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

depth first spanning treesparallel algorithmplanar graphsPRAM

Mathematics Subject Classification ID

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

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

(23)

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

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)