On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
type: Item
instance of: scholarly article
title: On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
zbMATH Open document ID: 1162.68027
author: Yury L. Orlovich
author: V. S. Gordon
author: Dominique De Werra
published in: Theoretical Computer Science
publication date: 2009-03-17T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5529526
zbMATH Keywords: independent dominating set
zbMATH Keywords: \(2P_{3}\)-free graph
zbMATH Keywords: perfect graph
zbMATH Keywords: approximability
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.11.023
OpenAlex ID: W1990831313
cites work: Q4258216
cites work: Q3941433
cites work: Independent domination in finitely defined classes of graphs
cites work: Q5422499
cites work: Graph Classes: A Survey
cites work: Independent Sets in Asteroidal Triple-Free Graphs
cites work: The weighted independent domination problem is NP-complete for chordal graphs
cites work: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
cites work: The strong perfect graph theorem
cites work: The complexity of theorem-proving procedures
cites work: Clustering and domination in perfect graphs
cites work: Q4511217
cites work: A note on the approximation of a minimum-weight maximal independent set
cites work: Independent domination in chordal graphs
cites work: Q4198056
cites work: Weakly triangulated graphs
cites work: Approximating the minimum maximal independence number
cites work: On approximating the minimum independent dominating set
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: Polar graphs and maximal independent sets
cites work: Satgraphs and independent domination. I
cites work: Independent domination in hereditary classes
cites work: Edge Dominating Sets in Graphs
DOI: 10.1016/J.TCS.2008.11.023
description: scientific article; zbMATH DE number 5529526