Geodesic
An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 297-327.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00471
Keywords: Vertex Separator, Grid Graph, External Memory 
@article{JGAA_2018_22_2_a6,
     author = {Junhao Gan and Yufei Tao},
     title = {An {I/O-Efficient} {Algorithm} for {Computing} {Vertex} {Separators} on {Multi-Dimensional} {Grid} {Graphs} and {Its} {Applications}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {297--327},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00471},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00471/}
}
TY  - JOUR
AU  - Junhao Gan
AU  - Yufei Tao
TI  - An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 297
EP  - 327
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00471/
DO  - 10.7155/jgaa.00471
LA  - en
ID  - JGAA_2018_22_2_a6
ER  - 
%0 Journal Article
%A Junhao Gan
%A Yufei Tao
%T An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
%J Journal of Graph Algorithms and Applications
%D 2018
%P 297-327
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00471/
%R 10.7155/jgaa.00471
%G en
%F JGAA_2018_22_2_a6
Junhao Gan; Yufei Tao. An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 297-327. doi : 10.7155/jgaa.00471. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00471/

Cité par Sources :