Recognizing breadth-first search trees in linear time

DOI10.1016/0020-0190(90)90155-QzbMATH Open0696.68065OpenAlexW1981097305MaRDI QIDQ911287FDOQ911287

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

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

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)

Cites Work

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

Cited In (13)

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

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)