Approximating theDomatic Number
From MaRDI portal
Publication:4785636
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)
68W40: Analysis of algorithms
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W20: Randomized algorithms
Related Items
Energy Efficient Monitoring in Sensor Networks, Disjoint dominating and total dominating sets in graphs, Hardness of \(k\)-vertex-connected subgraph augmentation problem, Energy efficient monitoring in sensor networks, An improved exact algorithm for the domatic number problem, 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, A survey of selected recent results on total domination in graphs, Remarks about disjoint dominating sets, Pairs of disjoint dominating sets and the minimum degree of graphs, Hardness and approximation results for packing Steiner trees, Edge-disjoint spanners in Cartesian products of graphs, Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
