An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications

DOI10.7155/jgaa.00471zbMath1394.05099OpenAlexW2883948692MaRDI QIDQ4585060

Junhao Gan, Yufei Tao

Publication date: 6 September 2018

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00471

zbMATH Keywords

graph separatorsmemory hierarchiesseparator-algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The general position number of integer lattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data mining. Concepts and techniques
• An external-memory depth-first search algorithm for general grid graphs
• New lower bounds for Hopcroft's problem
• An external memory data structure for shortest path queries
• Blocking for external graph searching
• On external-memory MST, SSSP and multi-way planar graph separation
• I/O-efficient batched union-find and its applications to terrain analysis
• I/O-Efficient Planar Separators
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• On the Hardness and Approximation of Euclidean DBSCAN
• A Network-Flow-Based Scheduler: Design, Performance History, and Experimental Analysis
• I/O-Efficient Algorithms on Near-Planar Graphs