Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
DOI10.1007/978-3-642-22953-4_25zbMath1342.68142OpenAlexW2103798048MaRDI QIDQ3088291
Martin Milanič, Ferdinando Cicalese, Ugo Vaccaro
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22953-4_25
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On positive influence dominating sets in social networks
- \(k\)-tuple total domination in graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- \(k\)-tuple domination in graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Local majorities, coalitions and monopolies in graphs: A review
- An analysis of the greedy algorithm for the submodular set covering problem
- Minimum monopoly in regular and tree graphs
- Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
- A threshold of ln n for approximating set cover
- FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
- Optimal File Sharing in Distributed Networks
- On Dominating Sets and Independent Sets of Graphs
- Automata, Languages and Programming
This page was built for publication: Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
