Approximation algorithms for connected dominating sets
From MaRDI portal
Publication:1386346
Recommendations
Cited in
(only showing first 100 items - show all)- Construction of strongly connected dominating sets in asymmetric multihop wireless networks
- A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem
- Connected domination of regular graphs
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- Algorithms for graphs with small octopus
- On approximability of the independent/connected edge dominating set problems
- Spanning trees with a constraint on the number of leaves. A new formulation
- Making a dominating set of a graph connected
- Two algorithms for minimum 2-connected r-hop dominating set
- A metaheuristic approach to the dominating tree problem
- The k-hop connected dominating set problem: approximation and hardness
- The probabilistic minimum dominating set problem
- Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
- Energy efficient low-cost virtual backbone construction for optimal routing in wireless sensor networks
- Regenerator location problem: polyhedral study and effective branch-and-cut algorithms
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- A distributed approximation algorithm for the bottleneck connected dominating set problem
- Solving the minimum M-dominating set problem by a continuous optimization approach based on DC programming and DCA
- A PTAS for minimum d-hop connected dominating set in growth-bounded graphs
- Wireless networking, dominating and packing
- On approximation of dominating tree in wireless sensor networks
- Nearly tight approximation algorithm for (connected) Roman dominating set
- 2-node-connectivity network design
- Approximating \(k\)-connected \(m\)-dominating sets
- A polynomial-time approximation to a minimum dominating set in a graph
- A game theoretic approach for minimal connected dominating set
- Improved budgeted connected domination and budgeted edge-vertex domination
- A polylogarithmic approximation algorithm for 2-edge-connected dominating set
- Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
- Algorithm and complexity of the two disjoint connected dominating sets problem on trees
- Approximating spanning trees with few branches
- On connected dominating sets of restricted diameter
- Complexity issues of variants of secure domination in graphs
- Revisiting connected dominating sets: an almost optimal local information algorithm
- On dominating sets whose induced subgraphs have a bounded diameter
- Routing-efficient CDS construction in disk-containment graphs
- Code updates based on minimal backbone and group key management for secure sensor networks
- On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- Message and time efficient multi-broadcast schemes
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Dominating problems in swapped networks
- On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks
- Construction of minimum edge-fault tolerant connected dominating set in a general graph
- Near-optimal dominating sets via random sampling
- 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
- An integer programming approach for fault-tolerant connected dominating sets
- Approximability results for the converse connected p-centre problem
- On the power of lookahead in greedy scheme for finding a minimum CDS for unit disk graphs
- On the structure of graphs vertex critical with~respect to connected domination
- Algorithms for minimum connected capacitated dominating set problem
- Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs
- A decomposition approach for the minimum connected dominating set problem
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- Finding totally independent spanning trees with linear integer programming
- New analysis and computational study for the planar connected dominating set problem
- An algorithm for the inverse distance-2 dominating set of a graph
- Pick, pack, \& survive: charging robots in a modern warehouse based on online connected dominating sets
- 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
- Minimum connected dominating sets of intervals on lines
- Connected domination
- Algorithms for Steiner connected dominating set problem based on learning automata theory
- Time efficient k-shot broadcasting in known topology radio networks
- MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- 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
- Max-leaves spanning tree is APX-hard for cubic graphs
- On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
- Connected dominating set. Theory and applications
- 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
- scientific article; zbMATH DE number 1163715 (Why is no real title available?)
- 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
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- scientific article; zbMATH DE number 2079403 (Why is no real title available?)
- scientific article; zbMATH DE number 2080196 (Why is no real title available?)
- Complexity and approximation of the connected set-cover problem
- Approximation algorithms for connected dominating sets
- Revisiting connected dominating sets: an optimal local algorithm?
- scientific article; zbMATH DE number 2172821 (Why is no real title available?)
- Computing an effective decision making group of a society using social network analysis
- The probabilistic min dominating set problem
- A matheuristic approach for solving the 2-connected dominating set problem
- Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
- A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
- Dominating sets and connected dominating sets in dynamic graphs
- 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
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- Completely independent spanning trees in some regular graphs
- Dominating an s-t-cut in a network
- TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
- Some results for the two disjoint connected dominating sets problem
- Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
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 Q1386346)
