scientific article; zbMATH DE number 2172821

MaRDI QIDQ4680214zbMATH OpenFDO

Authors Ning Chen, Jie Meng, Jiawei Rong, Hong Zhu

Publication date 2 June 2006

zbMATH Keywords

approximationcomplexitydominating setnon-approximability

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms – ESA 2004
• Parameterized approximation of dominating set problems
• On the parameterized complexity of approximating dominating set
• On the Parameterized Complexity of Approximating Dominating Set
• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Approximation hardness of dominating set problems in bounded degree graphs
• Approximating k-Connected m-Dominating Sets
• Approximating \(k\)-connected \(m\)-dominating sets

Cited in

(1)

• Weighted domination models and randomized heuristics

This page was built for publication:

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