Capacitated domination: problem complexity and approximation algorithms (Q2345937): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00453-013-9844-6
+Normal rank
@@ Property / OpenAlex ID @@
+W2095525633
@@ Property / OpenAlex ID: W2095525633 / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Polynomial-time data reduction for dominating set
@@ Property / cites work: Polynomial-time data reduction for dominating set / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+A linear time algorithm for finding tree-decompositions of small treewidth
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+On embedding an outer-planar graph in a point set
@@ Property / cites work: On embedding an outer-planar graph in a point set / rank @@
+Normal rank
@@ Property / cites work @@
+Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for capacitated facility location problems
+Normal rank
@@ Property / cites work @@
+Covering Problems with Hard Capacities
@@ Property / cites work: Covering Problems with Hard Capacities / rank @@
+Normal rank
@@ Property / cites work @@
+Capacitated Domination Faster Than O(2 n )
@@ Property / cites work: Capacitated Domination Faster Than O(2 n ) / rank @@
+Normal rank
@@ Property / cites work @@
+Subexponential parameterized algorithms on bounded-genus graphs and             <i>H</i>             -minor-free graphs
+Normal rank
@@ Property / cites work @@
+Capacitated Domination and Covering: A Parameterized Perspective
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+On the complexity of some colorful problems parameterized by treewidth
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
+Normal rank
@@ Property / cites work @@
+An improved approximation algorithm for vertex cover with hard capacities
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Capacitated vertex covering
@@ Property / cites work: Capacitated vertex covering / rank @@
+Normal rank
@@ Property / cites work @@
+Linear Problem Kernels for NP-Hard Problems on Planar Graphs
+Normal rank
@@ Property / cites work @@
+Simpler Linear-Time Kernelization for Planar Dominating Set
+Normal rank
@@ Property / cites work @@
+Q4368728
@@ Property / cites work: Q4368728 / rank @@
+Normal rank
@@ Property / cites work @@
+Domination in Graphs Applied to Electric Power Networks
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Set Covering and Vertex Cover Problems
+Normal rank
@@ Property / cites work @@
+Efficient Planarity Testing
@@ Property / cites work: Efficient Planarity Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Q5743430
@@ Property / cites work: Q5743430 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Capacitated Domination Problem
+Normal rank
@@ Property / cites work @@
+Capacitated Domination: Constant Factor Approximations for Planar Graphs
+Normal rank
@@ Property / cites work @@
+Capacitated domination problem
@@ Property / cites work: Capacitated domination problem / rank @@
+Normal rank
@@ Property / cites work @@
+Treewidth. Computations and approximations
@@ Property / cites work: Treewidth. Computations and approximations / rank @@
+Normal rank
@@ Property / cites work @@
+Computing and Combinatorics
@@ Property / cites work: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3898496
@@ Property / cites work: Q3898496 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526991
@@ Property / cites work: Q4526991 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
+Normal rank
@@ Property / cites work @@
+Q4782696
@@ Property / cites work: Q4782696 / rank @@
+Normal rank
@@ Property / cites work @@
+A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
+Normal rank