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 (47)

Dominating an \(s\)-\(t\)-cut in a network
Improving construction for connected dominating set with Steiner tree in wireless sensor networks
Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
Greedy approximation for the minimum connected dominating set with labeling
Near-optimal distributed approximation of minimum-weight connected 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
Algorithms for Steiner connected dominating set problem based on learning automata theory
Algorithmic aspects of secure connected domination in graphs
A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
Connected dominating set. Theory and applications
A matheuristic approach for solving the 2-connected dominating set problem
Minimum connected dominating sets in finite graphs
Title not available (Why is that?)
On connected domination in unit ball graphs
Complexity and approximation of the connected set-cover problem
The probabilistic min dominating set problem
A polylogarithmic approximation algorithm for 2-edge-connected dominating set
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\)
Revisiting connected dominating sets: an optimal local algorithm?
An exact algorithm for the maximum leaf spanning tree problem.
The probabilistic minimum dominating set problem
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
Wireless networking, dominating and packing
Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
Nearly tight approximation algorithm for (connected) Roman dominating set
Revisiting connected dominating sets: an almost optimal local information algorithm
On approximation of dominating tree in wireless sensor networks
Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem
Algorithm and complexity of the two disjoint connected dominating sets problem on trees
The maximum-leaf spanning tree problem: Formulations and facets
Connected dominating set in hypergraph
Dominating problems in swapped networks

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)