NP-completeness results for partitioning a graph into total dominating sets
From MaRDI portal
Publication:5918107
DOI10.1016/j.tcs.2018.04.006zbMath1433.68159OpenAlexW3023108549MaRDI QIDQ5918107
Petteri Laakkonen, Juho Lauri, Mikko Koivisto
Publication date: 7 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/307255
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) 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)
Related Items
On domatic and total domatic numbers of Cartesian products of graphs, Disjoint total dominating sets in near‐triangulations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Coupon coloring of some special graphs
- Kernel bounds for disjoint cycles and disjoint paths
- Clustering wireless ad hoc networks with weakly connected dominating set
- A survey of selected recent results on total domination in graphs
- On problems without polynomial kernels
- Some simplified NP-complete graph problems
- The domatic number problem on some perfect graph families
- Threshold graphs and related topics
- Inclusion/exclusion meets measure and conquer
- On coupon colorings of graphs
- 2-colorings in \(k\)-regular \(k\)-uniform hypergraphs
- Domination in generalized Petersen graphs
- Domatic Partition on Several Classes of Graphs
- Deploying Robots With Two Sensors inK1, 6-Free Graphs
- Graph-theoretic parameters concerning domination, independence, and irredundance
- New upper bounds on the decomposability of planar graphs
- Set Partitioning via Inclusion-Exclusion
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Total domination in graphs
- NP completeness of finding the chromatic index of regular graphs
- Total Domination in Graphs
- Combinatorial bounds via measure and conquer
- Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
- Parameterized Algorithms
- NP-completeness results for partitioning a graph into total dominating sets
- Faster graph coloring in polynomial space
