Complexity of Total {k}-Domination and Related Problems

DOI10.1007/978-3-642-21204-8_18zbMath1329.68141OpenAlexW87765976MaRDI QIDQ3004664

Hongyu Liang, Jing (Selena) He

Publication date: 3 June 2011

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21204-8_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (6)

A new approach on locally checkable problems ⋮ Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs ⋮ Total \(\{k\}\)-domination in special graphs ⋮ On the global total $k$-domination number of graphs ⋮ On the complexity of the labeled domination problem in graphs ⋮ On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The total \(\{k\}\)-domatic number of a graph
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• On the total \(\{k\}\)-domination number of Cartesian products of graphs
• Generalized domination and efficient domination in graphs
• The total \(\{k\}\)-domatic number of wheels and complete graphs
• On the total \(\{ k\} \)-domination and total \(\{ k\} \)-domatic number of graphs
• A threshold of ln n for approximating set cover
• Total domination in graphs
• Approximating theDomatic Number

This page was built for publication: Complexity of Total {k}-Domination and Related Problems