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 (2)

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

This page was built for publication: Recognizing graph search trees