The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Miller [9] propôs um algoritmo de tempo linear para calcular pequenos separadores para grafos planares 2 conectados. Explicamos seu algoritmo e apresentamos uma maneira de modificá-lo para uma versão com eficiência de espaço. Nosso algoritmo pode ser considerado como uma redução do espaço logarítmico desde a construção do separador até a construção da primeira árvore de busca em largura.
Ryo ASHIDA
Tokyo Institute of Technology
Sebastian KUHNERT
Humboldt University of Berlin
Osamu WATANABE
Tokyo Institute of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Ryo ASHIDA, Sebastian KUHNERT, Osamu WATANABE, "A Space-Efficient Separator Algorithm for Planar Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1007-1016, September 2019, doi: 10.1587/transfun.E102.A.1007.
Abstract: Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1007/_p
Copiar
@ARTICLE{e102-a_9_1007,
author={Ryo ASHIDA, Sebastian KUHNERT, Osamu WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Space-Efficient Separator Algorithm for Planar Graphs},
year={2019},
volume={E102-A},
number={9},
pages={1007-1016},
abstract={Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.},
keywords={},
doi={10.1587/transfun.E102.A.1007},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - A Space-Efficient Separator Algorithm for Planar Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1007
EP - 1016
AU - Ryo ASHIDA
AU - Sebastian KUHNERT
AU - Osamu WATANABE
PY - 2019
DO - 10.1587/transfun.E102.A.1007
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - Miller [9] proposed a linear-time algorithm for computing small separators for 2-connected planar graphs. We explain his algorithm and present a way to modify it to a space efficient version. Our algorithm can be regarded as a log-space reduction from the separator construction to the breadth first search tree construction.
ER -