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

DOI10.1016/j.tcs.2006.12.022zbMath1162.05358OpenAlexW2057543761MaRDI 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 algorithmsI/O-complexityexternal-memory algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Information storage and retrieval of data (68P20)

Related Items (3)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An external-memory depth-first search algorithm for general grid graphs