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