A linear-processor algorithm for depth-first search in planar graphs

DOI10.1016/0020-0190(88)90048-8zbMath0656.68069OpenAlexW2170132497MaRDI QIDQ1110342

Gregory E. Shannon

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1634&context=cstech

zbMATH Keywords

planar graphsparallel algorithmdepth-first-searchcyclic separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs, An optimal parallel algorithm for planar cycle separators, Not all planar digraphs have small cycle separators, Fast and compact planar embeddings

Cites Work

• Unnamed Item
• Unnamed Item
• Routing, merging, and sorting on parallel models of computation
• Finding small simple cycle separators for 2-connected planar graphs
• Parallel concepts in graph theory
• An Efficient Parallel Biconnectivity Algorithm
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Separator Theorem for Planar Graphs
• Finding the maximum, merging, and sorting in a parallel computation model
• Depth-First Search and Linear Graph Algorithms