Approximating theDomatic Number

DOI10.1137/S0097539700380754zbMath1021.05072MaRDI QIDQ4785636

Aravind Srinivasan, Magnús M. Halldórsson, Guy Kortsarz, Uriel Feige

Publication date: 5 January 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

probabilistic analysisdominationapproximation algorithmsdomatic number

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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) Randomized algorithms (68W20)

Related Items

Computing Roman domatic number of graphs ⋮ Hardness and approximation results for packing Steiner trees ⋮ Algorithmic Aspects of Private Bayesian Persuasion. ⋮ A Characterization of Visibility Graphs for Pseudo-polygons ⋮ An improved exact algorithm for the domatic number problem ⋮ Unsplittable coverings in the plane ⋮ Deploying Robots With Two Sensors inK_{1, 6}-Free Graphs ⋮ A note on near-optimal coloring of shift hypergraphs ⋮ A note on non-dominating set partitions in graphs ⋮ Disjoint dominating and total dominating sets in graphs ⋮ Hardness of \(k\)-vertex-connected subgraph augmentation problem ⋮ Pairs of disjoint dominating sets in connected cubic graphs ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ Packing strong subgraph in digraphs ⋮ Energy efficient monitoring in sensor networks ⋮ On the difference between chromatic number and dynamic chromatic number of graphs ⋮ Pairs of disjoint dominating sets and the minimum degree of graphs ⋮ Dominating and total dominating partitions in cubic graphs ⋮ Complexity of Total {k}-Domination and Related Problems ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Complete partitions of graphs ⋮ Decomposition of multiple coverings into many parts ⋮ Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs ⋮ Edge-disjoint spanners in Cartesian products of graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications ⋮ Energy Efficient Monitoring in Sensor Networks ⋮ Partitioning the Vertices of a Graph into Two Total Dominating Sets ⋮ Remarks about disjoint dominating sets ⋮ Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets ⋮ Unnamed Item