• An external-memory depth-first...

Result: An external-memory depth-first search algorithm for general grid graphs

Title:
An external-memory depth-first search algorithm for general grid graphs
Authors:
Jun-Ho Her, R. S. Ramakrishna
Source:
Theoretical Computer Science. 374:170-180
Publisher Information:
Elsevier BV, 2007.
Publication Year:
2007
Subject Terms:
0211 other engineering and technologies, I/O-complexity, External-memory algorithms, 0102 computer and information sciences, 02 engineering and technology, Graph algorithms, 01 natural sciences, Theoretical Computer Science, Computer Science(all)
Document Type:
Academic journal Article
Language:
English
ISSN:
0304-3975
DOI:
10.1016/j.tcs.2006.12.022
Access URL:
https://www.sciencedirect.com/science/article/abs/pii/S0304397506009108
https://dblp.uni-trier.de/db/journals/tcs/tcs374.html#HerR07
https://core.ac.uk/display/82555148
https://www.infona.pl/resource/bwmeta1.element.elsevier-244eecb1-938e-3f89-b095-0d89f0c2b321
https://doi.org/10.1016/j.tcs.2006.12.022
https://www.sciencedirect.com/science/article/pii/S0304397506009108
Rights:
Elsevier Non-Commercial
Accession Number:
edsair.doi.dedup.....b7a761cf4a3e73e3f4e3fae5a3975c8c
Database:
OpenAIRE

Further Information

Graph data in modern scientific and engineering applications are often too large to fit in the computer’s main memory. Input/output (I/O) complexity is a major research issue in this context. Minimization of the number of I/O operations (in external memory graph algorithms) is the main focus of current research while classical (internal memory) graph algorithms were designed to minimize temporal complexity.In this paper, we propose an external memory depth first search algorithm for general grid graphs. The I/O-complexity of the algorithm is O(sort(N)log2NM), where N=|V|+|E|, sort(N)=Θ(NBlogM/BNB) is the sorting I/O-complexity, M is the memory size, and B is the block size. The best known algorithm for this class of graph is the standard (internal memory) DFS algorithm with appropriate block (sub-grid) I/O-access. Its I/O-complexity is O(N/B). Recently, the authors proposed an O(sort(N)) algorithm for solid grid graphs.