Approximation algorithms for connected dominating sets

DOI10.1007/3-540-61680-2_55MaRDI QIDQ4595486zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Samir Khuller

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

Mathematics Subject Classification ID

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)

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

Cited in

(48)

• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Dominating an s-t-cut in a network
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• Greedy approximation for the minimum connected dominating set with labeling
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Near-optimal distributed approximation of minimum-weight connected dominating set
• On the Parameterized Complexity of Approximating Dominating Set
• Approximating \(k\)-connected \(m\)-dominating sets
• A unified greedy approximation for several dominating set problems
• Algorithms for Steiner connected dominating set problem based on learning automata theory
• Algorithmic aspects of secure connected domination in graphs
• Connected dominating set. Theory and applications
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Minimum connected dominating sets in finite graphs
• A matheuristic approach for solving the 2-connected dominating set problem
• On connected domination in unit ball graphs
• scientific article; zbMATH DE number 2080196 (Why is no real title available?)
• Complexity and approximation of the connected set-cover problem
• The probabilistic min dominating set problem
• Algorithms for graphs with small octopus
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• Approximation Algorithms and Hardness for Domination with Propagation
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• Leafy spanning \(k\)-forests
• scientific article; zbMATH DE number 2172821 (Why is no real title available?)
• Solving Connected Dominating Set Faster Than 2 n
• Approximation hardness of dominating set problems in bounded degree graphs
• A greedy approximation for minimum connected dominating sets
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Computing and Combinatorics
• 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.
• The probabilistic minimum dominating set problem
• Revisiting connected dominating sets: an optimal local algorithm?
• 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
• A polynomial-time approximation to a minimum dominating set in a graph
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Nearly tight approximation algorithm for (connected) Roman dominating set
• On approximation of dominating tree in wireless sensor networks
• Revisiting connected dominating sets: an almost optimal local information algorithm
• 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
• Dominating problems in swapped networks
• Connected dominating set in hypergraph

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)