On the approximability and exact algorithms for vector domination and related problems in graphs
From MaRDI portal
Publication:1946216
DOI10.1016/j.dam.2012.10.007zbMath1262.05116arXiv1012.1529OpenAlexW2002811283MaRDI QIDQ1946216
Ugo Vaccaro, Ferdinando Cicalese, Martin Milanič
Publication date: 18 April 2013
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.1529
approximation algorithmpolynomial time algorithmtreesinapproximability\(\alpha \)-dominationthreshold graphsmultiple domination\(k\)-domination\(P_{4}\)-free graphstotal vector dominationvector domination
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
(Total) vector domination for graphs with bounded branchwidth, Tuple domination on graphs with the consecutive-zeros property, Approximation algorithm and hardness results for defensive domination in graphs, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Generalized threshold processes on graphs, Domination parameters with number 2: interrelations and algorithmic consequences, Pervasive domination, Domination and convexity problems in the target set selection model, Latency-bounded target set selection in social networks, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Subexponential fixed-parameter algorithms for partial vector domination, Approximation algorithms for highly connected multi-dominating sets in unit disk graphs, Vector domination in split-indifference graphs, Multiple Domination, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, On the complexity of the vector connectivity problem
