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

DOI10.1137/0217028MaRDI QIDQ3798262zbMATH OpenOpenAlexFDO

Authors 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

parallel algorithmplanar graphsPRAMdepth first spanning trees

Mathematics Subject Classification ID

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

Recommendations

• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• Improved parallel depth-first search in undirected planar graphs
• A linear-processor algorithm for depth-first search in planar graphs
• Optimal parallel algorithms on planar graphs

Cited in

(22)

• Improved parallel depth-first search in undirected planar graphs
• Extending planar graph algorithms to \(K_{3,3}\)-free graphs
• Optimal parallel algorithms on planar graphs
• Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• An efficient parallel algorithm for shifting the root of a depth first spanning tree
• scientific article; zbMATH DE number 4060742 (Why is no real title available?)
• Not all planar digraphs have small cycle separators
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• Planar Strong Connectivity Helps in Parallel Depth-First Search
• A parallel algorithm for recognizing unordered depth-first search
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• scientific article; zbMATH DE number 1117869 (Why is no real title available?)
• scientific article; zbMATH DE number 1960881 (Why is no real title available?)
• Planar Depth-First Search in $O(\log n)$ Parallel Time
• An optimal parallel algorithm for planar cycle separators
• Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• Series - parallel graphs and depth-first search trees
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• Parallel search algorithms for graphs and trees
• A linear-processor algorithm for depth-first search in planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798262)