On the complexity of the minimum outer-connected dominating set problem in graphs

DOI10.1007/s10878-013-9703-zzbMath1360.90227OpenAlexW2094446349MaRDI QIDQ5963605

No author found.

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9703-z

zbMATH Keywords

dominating setNP-completeAPX-completeouter-connected dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (4)

Complexity of total outer-connected domination problem in graphs ⋮ Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem ⋮ Domination and outer connected domination in maximal outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the outer-connected domination in graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Total outer-connected domination numbers of trees
• Optimization, approximation, and complexity classes
• On the total outer-connected domination in graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Total outer-connected domination in trees
• A threshold of ln n for approximating set cover
• Reducibility among Combinatorial Problems
• Non-approximability results for optimization problems on bounded degree instances

This page was built for publication: On the complexity of the minimum outer-connected dominating set problem in graphs