A characterization of chain probe graphs

DOI10.1007/s10479-009-0584-6zbMath1250.05078OpenAlexW2071792782MaRDI QIDQ646709

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

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)

Related Items (5)

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 probe problem for \((r,\ell )\)-well-coveredness ⋮ Two characterizations of chain partitioned probe graphs ⋮ On the bi-enhancement of chordal-bipartite probe graphs

Uses Software

• IMP

Cites Work

• On probe interval graphs
• Algorithmic graph theory and perfect graphs
• Chordal probe graphs
• Threshold graphs and related topics
• 2-tree probe interval graphs have a large obstruction set
• Characterisations and Linear-Time Recognition of Probe Cographs
• Probe Ptolemaic Graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Node-Deletion Problems on Bipartite Graphs
• Graph Classes: A Survey
• Graph Sandwich Problems
• Computing and Combinatorics
• Difference graphs
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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