The recognition problem of graph search trees
DOI10.1137/20M1313301zbMATH Open1467.05032OpenAlexW3174133701MaRDI QIDQ4997136FDOQ4997136
Authors: Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler 
Publication date: 28 June 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1313301
Recommendations
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Nonnumerical algorithms (68W05)
Cites Work
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Depth-First Search and Linear Graph Algorithms
- Algorithmic graph theory and perfect graphs
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Efficient Planarity Testing
- Edge-disjoint spanning trees and depth-first search
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Depth-first search is inherently sequential
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for weakly triangulated graphs
- The LBFS structure and recognition of interval graphs
- A new LBFS-based algorithm for cocomparability graph recognition
- On computing the diameter of real-world undirected graphs
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- A Unified View of Graph Searching
- Distance approximating spanning trees
- Graph algorithms. Edited by Guy Even. With a foreword by Richard M. Karp
- Influence of the tie-break rule on the end-vertex problem
- On end-vertices of lexicographic breadth first searches
- A random NC algorithm for depth first search
- Some aspects of perfect elimination orderings in chordal graphs
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
- Recognizing breadth-first search trees in linear time
- Characterising AT-free graphs with BFS
- Linear time LexDFS on cocomparability graphs
- On the end-vertex problem of graph searches
Cited In (10)
- Recognizing LBFS trees of bipartite graphs
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
- Recognizing breadth-first search trees in linear time
- Graph-Theoretic Concepts in Computer Science
- On the recognition of search trees generated by BFS and DFS
- Linearizing partial search orders
- On the end-vertex problem of graph searches
- Graph Search Trees and Their Leaves
- A Unified View of Graph Searching
- Graph approach to solving problems of combinatorial recognition
Uses Software
This page was built for publication: The recognition problem of graph search trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997136)
