Recognizing breadth-first search trees in linear time

DOI10.1016/0020-0190(90)90155-QMaRDI QIDQ911287zbMATH OpenOpenAlexFDO

Authors 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) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Recommendations

• The recognition problem of graph search trees
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• scientific article; zbMATH DE number 1960881
• Parallel breadth-first search algorithms for trees and graphs

Cites work

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

Cited in

(13)

• Semi-dynamic shortest paths and breadth-first search in digraphs
• The Level-Ancestor problem on pure pointer machines
• Recognizing LBFS trees of bipartite graphs
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Semi-dynamic breadth-first search in digraphs
• Graph Search Trees and Their Leaves
• Certification of breadth-first algorithms by extraction
• Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
• Unrestricted and complete breadth-first search of trapezoid graphs in \(O(n)\) time
• Recognizing graph search trees
• The recognition problem of graph search trees
• Finding level-ancestors in trees
• On the recognition of search trees generated by BFS and DFS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911287)