A new LBFS-based algorithm for cocomparability graph recognition

DOI10.1016/j.dam.2015.07.016zbMath1350.05166OpenAlexW2193295754MaRDI QIDQ344849

Jérémie Dusart, Michel A. Habib

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.07.016

zbMATH Keywords

cocomparability graphscomparability graphsgraph search \(\mathrm{LBFS}^+\)graph search LBFStransitive orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (11)

Recognizing graph search trees ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Perfect elimination orderings for symmetric matrices ⋮ Linearizing partial search orders ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ A tie-break model for graph search ⋮ A new graph parameter to measure linearity ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ The Recognition Problem of Graph Search Trees ⋮ Graph Classes and Forbidden Patterns on Three Vertices

Cites Work

• An optimal greedy heuristic to color interval graphs
• A unified approach to domination problems on interval graphs
• Modular decomposition and transitive orientation
• Efficient graph representations
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• 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
• Domination on Cocomparability Graphs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A new LBFS-based algorithm for cocomparability graph recognition