Approximating theDomatic Number
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Recommendations
Cited in
(41)- Approximation in (poly-) logarithmic space
- Dominating an s-t-cut in a network
- Energy efficient monitoring in sensor networks
- Inapproximability results for combinatorial auctions with submodular utility functions
- Disjoint dominating and total dominating sets in graphs
- An improved exact algorithm for the domatic number problem
- Mathematical Foundations of Computer Science 2005
- Algorithms – ESA 2004
- Complete partitions of graphs
- Deploying robots with two sensors in \(K_{1,6}\)-free graphs
- Computing Roman domatic number of graphs
- A note on near-optimal coloring of shift hypergraphs
- A survey of selected recent results on total domination in graphs
- Approximating fault-tolerant domination in general graphs
- A characterization of visibility graphs for pseudo-polygons
- On the difference between chromatic number and dynamic chromatic number of graphs
- Partitioning the vertices of a graph into two total dominating sets
- Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs
- Multi-constructor CMSA for the maximum disjoint dominating sets problem
- Algorithms with large domination ratio
- A note on non-dominating set partitions in graphs
- Decomposition of multiple coverings into many parts
- Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
- Pairs of disjoint dominating sets in connected cubic graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
- Remarks about disjoint dominating sets
- Pairs of disjoint dominating sets and the minimum degree of graphs
- Domination analysis for minimum multiprocessor scheduling
- Energy Efficient Monitoring in Sensor Networks
- Packing strong subgraph in digraphs
- Approximating the domatic number
- Complexity of Total {k}-Domination and Related Problems
- Dominating and total dominating partitions in cubic graphs
- Almost polynomial hardness of node-disjoint paths in grids
- Approximations of the domination number of a graph
- Edge-disjoint spanners in Cartesian products of graphs
- Hardness and approximation results for packing Steiner trees
- Algorithmic aspects of private Bayesian persuasion
- Hardness of \(k\)-vertex-connected subgraph augmentation problem
- Domatic partitions and the Lovász local lemma
This page was built for publication: Approximating theDomatic Number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4785636)
