Paper Info
Title
A Space-Efficient Separator Algorithm For Planar Graphs
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.
Year
DOI
Venue
2019
10.1587/transfun.E102.A.1007
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
separator, sublinear-space algorithm
Discrete mathematics,Separator (oil production),Planar graph,Mathematics
Journal
Volume
Issue
ISSN
E102A
9
0916-8508
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Ryo Ashida100.34
Sebastian Kuhnert2366.52
Osamu Watanabe3960104.55