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

DOI10.1016/j.tcs.2006.12.022zbMath1162.05358MaRDI QIDQ1022598

Jun-Ho Her, R. S. Ramakrishna

Publication date: 22 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.12.022

zbMATH Keywords

graph algorithms; I/O-complexity; external-memory algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

68P20: Information storage and retrieval of data

Related Items

An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications, A new constraint programming approach for optimising a coal rail system, A job-shop scheduling approach for optimising sugarcane rail operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• External-memory depth-first search algorithm for solid grid graphs
• Finding small simple cycle separators for 2-connected planar graphs
• Algorithms for memory hierarchies. Advanced lectures
• An external memory data structure for shortest path queries
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel algorithms for planar graph isomorphism and related problems
• On External-Memory Planar Depth First Search
• I/O-Efficient Algorithms for Problems on Grid-Based Terrains