Planar Depth-First Search in $O(\log n)$ Parallel Time

DOI10.1137/0219047zbMath0697.68037OpenAlexW2023670982MaRDI QIDQ3474884

Torben Hagerup

Publication date: 1990

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

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

zbMATH Keywords

planar graphsparallel computingdepth-first searchPriority CRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items (9)

A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ An optimal parallel algorithm for planar cycle separators ⋮ A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH ⋮ Depth-first search in directed planar graphs, revisited ⋮ Parallel approximation schemes for problems on planar graphs ⋮ Parallel search algorithms for graphs and trees ⋮ Fast and compact planar embeddings ⋮ IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH

This page was built for publication: Planar Depth-First Search in $O(\log n)$ Parallel Time