Local reorientation, global order, and planar topology

Ming Yang Kao*, Gregory E. Shannon

*Corresponding author for this work

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

7 Scopus citations

Abstract

Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected components of a digraph and compute directed spanning trees for these components. This paper provides the first non-trivial partial solution to this open problem: For a planar digraph with n vertices, the strongly connected components can be computed in O(log3 n) time and O(n) processors. If the graph is strongly connected, a directed spanning tree can be built in O(log2 n) time and O(n) processors. Both algorithms are deterministic and run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory.

Original languageEnglish (US)
Title of host publicationProc Twenty First Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages286-296
Number of pages11
ISBN (Print)0897913078
StatePublished - Dec 1 1989
EventProceedings of the Twenty First Annual ACM Symposium on Theory of Computing - Seattle, WA, USA
Duration: May 15 1989May 17 1989

Publication series

NameProc Twenty First Annu ACM Symp Theory Comput

Other

OtherProceedings of the Twenty First Annual ACM Symposium on Theory of Computing
CitySeattle, WA, USA
Period5/15/895/17/89

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Local reorientation, global order, and planar topology'. Together they form a unique fingerprint.

Cite this