A characterization of chain probe graphs

DOI10.1007/S10479-009-0584-6MaRDI QIDQ646709zbMATHOpenAlexFDO

Authors Martin Charles Golumbic, Frédéric Maffray, Grégory Morel

Publication date 17 November 2011

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-009-0584-6

zbMATH Keywords

chain graphindependent set of verticeschain probe graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Two characterizations of chain partitioned probe graphs
• Chordal probe graphs (extended abstract)
• On the bi-enhancement of chordal-bipartite probe graphs
• Chordal probe graphs
• Probe threshold and probe trivially perfect graphs

Cites work

• scientific article; zbMATH DE number 2117210 (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 polynomial time recognition algorithm for probe interval graphs
• Algorithmic graph theory and perfect graphs
• Characterisations and Linear-Time Recognition of Probe Cographs
• Chordal probe graphs
• Chordal probe graphs (extended abstract)
• Computing and Combinatorics
• Difference graphs
• Graph Classes: A Survey
• Graph Sandwich Problems
• Node-Deletion Problems on Bipartite Graphs
• On probe interval graphs
• Probe Ptolemaic Graphs
• Probe split graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Threshold graphs and related topics
• Two tricks to triangulate chordal probe graphs in polynomial time

Cited in

(5)

• Two characterizations of chain partitioned probe graphs
• On the probe problem for \((r,\ell )\)-well-coveredness
• On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• On the bi-enhancement of chordal-bipartite probe graphs

Describes a project that uses

Uses Software

• IMP

This page was built for publication: A characterization of chain probe graphs

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