Approximation algorithms for connected dominating sets
From MaRDI portal
Publication:1386346
DOI10.1007/PL00009201zbMath0895.68106OpenAlexW3141863997WikidataQ59442093 ScholiaQ59442093MaRDI QIDQ1386346
Publication date: 8 September 1998
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009201
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (only showing first 100 items - show all)
Connected domination in random graphs ⋮ Nordhaus-Gaddum-type results on the connected edge domination number ⋮ BROADCASTING IN AD HOC NETWORKS BASED ON SELF-PRUNING ⋮ A ZONAL ALGORITHM FOR CLUSTERING AN HOC NETWORKS ⋮ A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS ⋮ Approximating k-Connected m-Dominating Sets ⋮ The wake up dominating set problem ⋮ 2-node-connectivity network design ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Constant-time distributed dominating set approximation ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ Greedy approximation for the minimum connected dominating set with labeling ⋮ Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ Dominating problems in swapped networks ⋮ Unnamed Item ⋮ Efficient respondents selection for biased survey using homophily-high social relation graph ⋮ Algorithms for Steiner Connected Dominating Set Problem Based on Learning Automata Theory ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ Searching for a cycle with maximum coverage in undirected graphs ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Making a dominating set of a graph connected ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Time efficient \(k\)-shot broadcasting in known topology radio networks ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks ⋮ A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ A metaheuristic approach to the dominating tree problem ⋮ A distributed approximation algorithm for the bottleneck connected dominating set problem ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Complexity issues of variants of secure domination in graphs ⋮ Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA ⋮ Revisiting connected dominating sets: an almost optimal local information algorithm ⋮ Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ On the complexity of the regenerator location problem treewidth and other parameters ⋮ A game theoretic approach for minimal connected dominating set ⋮ Approximability results for the converse connectedp-centre problem† ⋮ Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks ⋮ On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks ⋮ On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs ⋮ A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ On the Structure of Graphs Vertex Critical with Respect to Connected Domination ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks ⋮ On the \((h,k)\)-domination numbers of iterated line digraphs ⋮ Wireless networking, dominating and packing ⋮ On approximation of dominating tree in wireless sensor networks ⋮ Energy efficient low-cost virtual backbone construction for optimal routing in wireless sensor networks ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Routing-efficient CDS construction in disk-containment graphs ⋮ A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem' ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ Code updates based on minimal backbone and group key management for secure sensor networks ⋮ An Algorithm for the Inverse Distance-2 Dominating Set of a Graph ⋮ On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs ⋮ Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks ⋮ Clustering the wireless ad hoc networks: a distributed learning automata approach ⋮ Computing an effective decision making group of a society using social network analysis ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ A 2-approximation algorithm for finding a spanning tree with maximum number of leaves ⋮ Completely independent spanning trees in some regular graphs ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ On parameterized independent feedback vertex set ⋮ Connected dominating sets on dynamic geometric graphs ⋮ A linear kernel for a planar connected dominating set ⋮ On connected domination in unit ball graphs ⋮ An exact algorithm for minimum CDS with shortest path constraint in wireless networks ⋮ A tight bound on the number of mobile servers to guarantee transferability among dominating configurations ⋮ A greedy approximation for minimum connected dominating sets ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Computing a tree having a small vertex cover ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ Unnamed Item ⋮ Improving construction for connected dominating set with Steiner tree in wireless sensor networks ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Message and time efficient multi-broadcast schemes ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS ⋮ Some results for the two disjoint connected dominating sets problem ⋮ Construction of strongly connected dominating sets in asymmetric multihop wireless networks ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem ⋮ Network verification via routing table queries ⋮ Connected Domination ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS ⋮ Connected domination of regular graphs ⋮ Cluster-Based Energy-Efficient Secure Routing in Wireless Sensor Networks
This page was built for publication: Approximation algorithms for connected dominating sets
