Characterisations and Linear-Time Recognition of Probe Cographs

DOI10.1007/978-3-540-74839-7_22zbMATH Open1141.68537OpenAlexW1557893657MaRDI QIDQ3508570FDOQ3508570

Authors: Van Bang Le, H. N. de Ridder 

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_22

Recommendations

• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Computing and Combinatorics
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
• Probe threshold and probe trivially perfect graphs
• Probe split graphs

Mathematics Subject Classification ID

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

Cites Work

• Graph Classes: A Survey
• Title not available (Why is that?)
• Weakly triangulated graphs
• A Linear Recognition Algorithm for Cographs
• Probe threshold and probe trivially perfect graphs
• Slim graphs
• Precoloring Extension III: Classes of Perfect Graphs
• On probe interval graphs
• Probe split graphs
• Chordal probe graphs
• A polynomial time recognition algorithm for probe interval graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing and Combinatorics
• 2-tree probe interval graphs have a large obstruction set
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• STACS 2005
• Theory and Applications of Models of Computation
• On slim graphs, even pairs, and star-cutsets
• A good characterization of cograph contractions
• Forbidden induced subgraph characterization of cograph contractions
• Partitioned Probe Comparability Graphs

Cited In (14)

• Computing and Combinatorics
• Probe split graphs
• Probe Ptolemaic Graphs
• Recognition of probe proper interval graphs
• Probe threshold and probe trivially perfect graphs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Certifying algorithms
• Recognition of Probe Ptolemaic Graphs
• A characterization of chain probe graphs
• Good characterizations and linear time recognition for 2-probe block graphs
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Induced betweenness in order-theoretic trees
• Linear-Time Recognition of Probe Interval Graphs

This page was built for publication: Characterisations and Linear-Time Recognition of Probe Cographs

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