Recognizing breadth-first search trees in linear time

DOI10.1016/0020-0190(90)90155-QzbMath0696.68065OpenAlexW1981097305MaRDI QIDQ911287

Udi Manber

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90155-q

zbMATH Keywords

graphstreesbreadth-first search

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 (8)

Finding level-ancestors in trees ⋮ Recognizing graph search trees ⋮ Semi-dynamic shortest paths and breadth-first search in digraphs ⋮ Unnamed Item ⋮ The Level-Ancestor problem on pure pointer machines ⋮ The Recognition Problem of Graph Search Trees ⋮ On the recognition of search trees generated by BFS and DFS ⋮ Semi-dynamic breadth-first search in digraphs

Cites Work

• Fast Algorithms for Finding Nearest Common Ancestors
• On Finding Lowest Common Ancestors: Simplification and Parallelization

This page was built for publication: Recognizing breadth-first search trees in linear time