IEICE TRANSACTIONS on Fundamentals
A Space-Efficient Separator Algorithm for Planar Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1007-1016
- Publication Date
- 2019/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.1007
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Graph algorithms
Authors
Ryo ASHIDA
Tokyo Institute of Technology
Sebastian KUHNERT
Humboldt University of Berlin
Osamu WATANABE
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
