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

Authors

  • Junhao Gan
  • Yufei Tao

DOI:

https://doi.org/10.7155/jgaa.00471

Keywords:

Vertex Separator , Grid Graph , External Memory

Abstract

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

Issue

Section

Articles

Categories