A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs

DOI10.1137/0217028zbMath0652.68082OpenAlexW2084593768MaRDI QIDQ3798262

Xin He, Yaacov Yesha

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217028

zbMATH Keywords

planar graphsparallel algorithmPRAMdepth first spanning trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (8)

Improved parallel depth-first search in undirected planar graphs ⋮ An optimal parallel algorithm for planar cycle separators ⋮ A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ Not all planar digraphs have small cycle separators ⋮ Parallel search algorithms for graphs and trees ⋮ Extending planar graph algorithms to \(K_{3,3}\)-free graphs ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

This page was built for publication: A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs