The price of connectivity for dominating set: upper bounds and complexity
From MaRDI portal
Publication:406321
DOI10.1016/j.dam.2014.05.029zbMath1297.05128arXiv1303.2868OpenAlexW2039349395MaRDI QIDQ406321
Eglantine Camby, Oliver Schaudt
Publication date: 8 September 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.2868
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Related Items (11)
A new characterization of \(P_k\)-free graphs ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ The Price of Connectivity for Cycle Transversals ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Unnamed Item ⋮ Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs ⋮ The price of connectivity for feedback vertex set ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ The price of connectivity for cycle transversals ⋮ Connected Domination ⋮ A proof of a conjecture on the connected domination number
Cites Work
- On graphs for which the connected domination number is at most the total domination number
- Characterization of \(P_{6}\)-free graphs
- A new characterization of \(P_{6}\)-free graphs
- Connected vertex covers in dense graphs
- Algorithmic graph theory and perfect graphs
- On a property of the class of n-colorable graphs
- On Hadwiger's Number and the Stability Number
- A semi-induced subgraph characterization of upper domination perfect graphs
- Perfect connected-dominant graphs
- A note on the characterization of domination perfect graphs
- The Price of Connectivity for Vertex Cover
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The price of connectivity for dominating set: upper bounds and complexity
