The Recognition Problem of Graph Search Trees
From MaRDI portal
Publication:4997136
DOI10.1137/20M1313301zbMath1467.05032OpenAlexW3174133701MaRDI QIDQ4997136
Martin Strehler, Nevena Pivač, Matjaž Krnc, Carolin Denkert, Ekkehard Köhler, Jesse Beisegel, Robert Scheffler
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
Trees (05C05) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A new LBFS-based algorithm for cocomparability graph recognition
- On computing the diameter of real-world undirected graphs
- Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
- Some aspects of perfect elimination orderings in chordal graphs
- Recognizing breadth-first search trees in linear time
- On end-vertices of lexicographic breadth first searches
- Depth-first search is inherently sequential
- A random NC algorithm for depth first search
- 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
- Characterising AT-free graphs with BFS
- Algorithmic graph theory and perfect graphs
- Algorithms for weakly triangulated graphs
- LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
- The LBFS Structure and Recognition of Interval Graphs
- Graph Algorithms
- Linear Time LexDFS on Cocomparability Graphs.
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Unified View of Graph Searching
- Efficient Planarity Testing
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Algorithmic Aspects of Vertex Elimination on Graphs
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Distance approximating spanning trees
- Depth-First Search and Linear Graph Algorithms
