@inproceedings{44f9de0bf8fe43d09a35aa91ebbf6749,
title = "All graphs have cycle separators and planar directed depth-first search is in DNC",
abstract = "All graphs have cycle separators. (A single vertex is regarded as a trivial cycle.) In sequential computation, a cycle separator can be found in O(n + e) time for any undirected graph of n vertices and e edges; in O((n + e) log n) time for any directed graph. In parallel computation, it is in deterministic NC to convert any depth-first search forest of any graph into a cycle separator. Moreover, finding a cycle separator for any planar directed graph is in deterministic NC; consequently, finding a depth-first search forest in any planar directed graph is in deterministic NC, too.",
author = "Kao, {Ming Yang}",
note = "Funding Information: *supported in part by a 1987 Summer Faculty Fellowship from Indiana University at Bloomington. Publisher Copyright: {\textcopyright} 1988, Springer-Verlag.; 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988 ; Conference date: 28-06-1988 Through 01-07-1988",
year = "1988",
doi = "10.1007/BFb0040373",
language = "English (US)",
isbn = "9780387968186",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "53--63",
editor = "Reif, {John H.}",
booktitle = "VLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings",
}