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

DOI10.1137/0217028zbMATH Open0652.68082OpenAlexW2084593768MaRDI QIDQ3798262FDOQ3798262

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

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

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)

Cited In (22)

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