On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
From MaRDI portal
Publication:1006083
DOI10.1016/j.tcs.2008.11.023zbMath1162.68027OpenAlexW1990831313MaRDI QIDQ1006083
Yury L. Orlovich, Valery S. Gordon, Dominique de Werra
Publication date: 17 March 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.11.023
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Mind the independence gap
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- On approximating the minimum independent dominating set
- Weakly triangulated graphs
- Satgraphs and independent domination. I
- Independent domination in hereditary classes
- The strong perfect graph theorem
- Polar graphs and maximal independent sets
- Clustering and domination in perfect graphs
- Independent domination in chordal graphs
- A note on the approximation of a minimum-weight maximal independent set
- Independent domination in finitely defined classes of graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Edge Dominating Sets in Graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Graph Classes: A Survey
- Independent Sets in Asteroidal Triple-Free Graphs
- The complexity of theorem-proving procedures
