Approximation algorithms for connected dominating sets

DOI10.1007/3-540-61680-2_55zbMATH Open1379.68352OpenAlexW2134003300MaRDI QIDQ4595486FDOQ4595486

Publication date: 5 December 2017

Published in: Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/830

Recommendations

Approximation algorithms for connected dominating sets
Approximating k-Connected m-Dominating Sets
Approximating \(k\)-connected \(m\)-dominating sets
A greedy approximation for minimum connected dominating sets
Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
Parameterized approximation of dominating set problems
Approximation algorithms for domination search
On the parameterized complexity of approximating dominating set
On the Parameterized Complexity of Approximating Dominating Set

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (27)

Improving construction for connected dominating set with Steiner tree in wireless sensor networks
TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
On the Parameterized Complexity of Approximating Dominating Set
A unified greedy approximation for several dominating set problems
Approximating \(k\)-connected \(m\)-dominating sets
Algorithmic aspects of secure connected domination in graphs
A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
Title not available (Why is that?)
Complexity and approximation of the connected set-cover problem
Algorithms for graphs with small octopus
Approximation Algorithms and Hardness for Domination with Propagation
Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
Leafy spanning \(k\)-forests
Solving Connected Dominating Set Faster Than 2 n
Title not available (Why is that?)
Computing and Combinatorics
Approximation hardness of dominating set problems in bounded degree graphs
Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
A greedy approximation for minimum connected dominating sets
Approximation algorithm for (connected) Italian dominating function
Solving connected dominating set faster than \(2^n\)
An exact algorithm for the maximum leaf spanning tree problem.
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
Nearly tight approximation algorithm for (connected) Roman dominating set
Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem
The maximum-leaf spanning tree problem: Formulations and facets

This page was built for publication: Approximation algorithms for connected dominating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595486)