All graphs have cycle separators and planar directed depth-first search is in DNC

Ming Yang Kao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationVLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings
EditorsJohn H. Reif
PublisherSpringer Verlag
Pages53-63
Number of pages11
ISBN (Print)9780387968186
DOIs
StatePublished - 1988
Event3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988 - Corfu, Greece
Duration: Jun 28 1988Jul 1 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume319 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1988
CountryGreece
CityCorfu
Period6/28/887/1/88

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'All graphs have cycle separators and planar directed depth-first search is in DNC'. Together they form a unique fingerprint.

Cite this