Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
From MaRDI portal
Publication:4202205
DOI10.1137/0222033zbMath0773.68041MaRDI QIDQ4202205
Gregory E. Shannon, Ming-Yang Kao
Publication date: 1 September 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222033
strong connectivity; vertex expansion; directed spanning trees; planar orientation; planar directed graphs; edge cutting; tree rerooting; vertex contraction; duplicate removal; linear-processor NC algorithms
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C99: Graph theory
68W15: Distributed algorithms
Related Items
Unnamed Item, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Topologically trivial closed walks in directed surface graphs