A new LBFS-based algorithm for cocomparability graph recognition

DOI10.1016/J.DAM.2015.07.016zbMATH Open1350.05166OpenAlexW2193295754MaRDI QIDQ344849FDOQ344849

Jérémie Dusart, Michel 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

Recommendations

• scientific article; zbMATH DE number 1305500
• On the power of graph searching for cocomparability graphs
• Linear time LexDFS on cocomparability graphs
• A simple linear time LexBFS cograph recognition algorithm.
• The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs

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)

Cites Work

• Graph Classes: A Survey
• Modular decomposition and transitive orientation
• Efficient graph representations
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Domination on Cocomparability Graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Title not available (Why is that?)
• An optimal greedy heuristic to color interval graphs
• A unified approach to domination problems on interval graphs
• On the power of graph searching for cocomparability graphs
• The LBFS Structure and Recognition of Interval Graphs
• A Simple Linear Time LexBFS Cograph Recognition Algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph-Theoretic Concepts in Computer Science

Cited In (17)

• Recognizing LBFS trees of bipartite graphs
• Title not available (Why is that?)
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• On the power of graph searching for cocomparability graphs
• The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
• Perfect elimination orderings for symmetric matrices
• Recognizing graph search trees
• Linearizing partial search orders
• A tie-break model for graph search
• Title not available (Why is that?)
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Semi-proper interval graphs
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• The Recognition Problem of Graph Search Trees
• A new graph parameter to measure linearity
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
• Graph Classes and Forbidden Patterns on Three Vertices

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344849)