Recognizing graph search trees

DOI10.1016/j.entcs.2019.08.010OpenAlexW2979077395WikidataQ113317422 ScholiaQ113317422MaRDI QIDQ2132337

Jesse Beisegel, Martin Strehler, Ekkehard Köhler, Nevena Pivač, Carolin Denkert, Matjaž Krnc, Robert Scheffler

Publication date: 27 April 2022

Full work available at URL: https://arxiv.org/abs/1811.09249

zbMATH Keywords

MCSMNSLBFSLDFSsearch tree recognition

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Related Items

Linearizing partial search orders, On the recognition of search trees generated by BFS and DFS

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• A new LBFS-based algorithm for cocomparability graph recognition
• On computing the diameter of real-world undirected graphs
• Recognizing breadth-first search trees in linear time
• On end-vertices of lexicographic breadth first searches
• 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
• 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
• Depth-First Search and Linear Graph Algorithms