External-memory breadth-first search with sublinear I/O

DOI10.1007/3-540-45749-6_63MaRDI QIDQ4411404zbMATH OpenFDO

Authors K. Mehlhorn, Ulrich Meyer

Publication date 8 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2461/24610723.htm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• External memory BFS on undirected graphs with bounded degree.
• scientific article; zbMATH DE number 1445387
• On dynamic breadth-first search in external-memory
• Improved external memory BFS implementations
• A computational study of external-memory BFS algorithms

Cited in

(23)

• Fast breadth-first search in still less space
• External memory BFS on undirected graphs with bounded degree.
• An implementation of I/O-efficient dynamic breadth-first search using level-aligned hierarchical clustering
• On Trade-Offs in External-Memory Diameter-Approximation
• Semi-external LTL Model Checking
• A computational study of external-memory BFS algorithms
• Design and Engineering of External Memory Traversal Algorithms for General Graphs
• Via Detours to I/O-Efficient Shortest Paths
• scientific article; zbMATH DE number 1305462 (Why is no real title available?)
• An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
• Theory and techniques for synthesizing efficient breadth-first search algorithms
• On dynamic breadth-first search in external-memory
• scientific article; zbMATH DE number 1445387 (Why is no real title available?)
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• External memory algorithms for finding disjoint paths in undirected graphs
• Improved external memory BFS implementations
• Design and implementation of a practical I/O-efficient shortest paths algorithm
• I/O-efficient data structures for colored range and prefix reporting
• Efficient semi-external depth-first search
• Optimal cache-oblivious mesh layouts
• Certifying induced subgraphs in large graphs
• Traversing graphs in a paging environment, BFS or DFS?
• I/O-efficient algorithms for graphs of bounded treewidth

This page was built for publication: External-memory breadth-first search with sublinear I/O

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4411404)