Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph

DOI10.1002/rsa.3240020207zbMath0731.68044OpenAlexW2030543286WikidataQ56324108 ScholiaQ56324108MaRDI QIDQ3357536

Martin Dyer, Alan M. Frieze

Publication date: 1991

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240020207

zbMATH Keywords

random graphlexicographically first depth first search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• Unnamed Item
• Parallelism and the maximal path problem
• A random NC algorithm for depth first search
• Parallel graph algorithms that are efficients on average
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets

This page was built for publication: Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph