An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
DOI:
https://doi.org/10.7155/jgaa.00471Keywords:
Vertex Separator , Grid Graph , External MemoryAbstract
A vertex separator, in general, refers to a set of vertices whose removal disconnects the original graph into subgraphs possessing certain nice properties. Such separators have proved useful for solving a variety of graph problems. The core contribution of the paper is an I/O-efficient algorithm that finds, on any $d$-dimensional grid graph, a small vertex separator which mimics the well-known separator of [Maheshwari and Zeh, SICOMP'08] for planar graphs. We accompany our algorithm with two applications. First, by integrating our separators with existing algorithms, we strengthen the current state-of-the-art results of three fundamental problems on 2D grid graphs: finding connected components, finding single source shortest paths, and breadth-first search. Second, we show how our separator-algorithm can be deployed to perform density-based clustering on $d$-dimensional points I/O-efficiently.Downloads
Download data is not yet available.
Downloads
Published
2018-01-01
How to Cite
Gan, J., & Tao, Y. (2018). An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications. Journal of Graph Algorithms and Applications, 22(2), 297–327. https://doi.org/10.7155/jgaa.00471
License
Copyright (c) 2018 Junhao Gan, Yufei Tao
This work is licensed under a Creative Commons Attribution 4.0 International License.