scientific article; zbMATH DE number 7651152

DOI10.4230/LIPIcs.ESA.2020.13MaRDI QIDQ5874479

Jesse Beisegel, Martin Strehler, Robert Scheffler, Ekkehard Köhler

Publication date: 7 February 2023

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

chordal graphssearch treesLexBFSLexDFSlinear time implementation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• A tie-break model for graph search
• Recognizing breadth-first search trees in linear time
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Moplex orderings generated by the LexDFs algorithm
• On the Power of Graph Searching for Cocomparability Graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• The LBFS Structure and Recognition of Interval Graphs
• Linear Time LexDFS on Cocomparability Graphs.
• A Unified View of Graph Searching
• Efficient Planarity Testing
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Recognition of Circle Graphs
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
• Depth-First Search and Linear Graph Algorithms
• DFS tree construction: Algorithms and characterizations