Characterisations and Linear-Time Recognition of Probe Cographs

DOI10.1007/978-3-540-74839-7_22zbMATH1141.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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(16)

• Induced betweenness in order-theoretic trees
• A characterization of chain probe graphs
• Probe Ptolemaic Graphs
• Certifying algorithms
• Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
• Good characterizations and linear time recognition for 2-probe block graphs
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• Recognition of probe proper interval graphs
• Probe threshold and probe trivially perfect graphs
• Probe split graphs
• Recognition of Probe Ptolemaic Graphs
• Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs
• Computing and Combinatorics
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• On the complexity of probe and sandwich problems for generalized threshold 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)