The k-hop connected dominating set problem: approximation and hardness

DOI10.1007/S10878-017-0128-YzbMATH Open1384.90081OpenAlexW2600384081MaRDI QIDQ1679503FDOQ1679503

Authors: Rafael S. Coelho, Phablo F. S. Moura, Yoshiko Wakabayashi 

Publication date: 9 November 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0128-y

Recommendations

• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Algorithm and hardness results on hop domination in graphs
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems

zbMATH Keywords

approximation algorithmshardness\(k\)-hop connected dominating set\(k\)-disruptive separator

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• Title not available (Why is that?)
• Graph Classes: A Survey
• Algorithmic graph theory and perfect graphs
• Max-leaves spanning tree is APX-hard for cubic graphs
• A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
• On the hardness of approximating minimum vertex cover
• Title not available (Why is that?)
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Listing all Minimal Separators of a Graph
• Bidimensionality: new connections between FPT algorithms and PTASs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Vertex and edge covers with clustering properties: Complexity and algorithms
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Approximation algorithms for connected dominating sets
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Enumeration of minimal dominating sets and variants
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Title not available (Why is that?)
• Steiner trees, connected domination and strongly chordal graphs
• Title not available (Why is that?)
• Approximation hardness of dominating set problems in bounded degree graphs
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• A greedy approximation for minimum connected dominating sets
• A unified approach to domination problems on interval graphs
• Generalized split graphs and Ramsey numbers
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Algorithms – ESA 2004
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Connected dominating set. Theory and applications
• Approximation and Online Algorithms
• Approximation and intractability results for the maximum cut problem and its variants
• Title not available (Why is that?)
• Minimal separators in \(P_4\)-sparse graphs
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• Permutation graphs: Connected domination and Steiner trees
• A linear time algorithm to list the minimal separators of chordal graphs
• Doubly chordal graphs, steiner trees, and connected domination
• Optimal dynamic program for \(r\)-domination problems over tree decompositions
• Connected domination and Steiner set on weighted permutation graphs
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
• Revisiting connected dominating sets: an optimal local algorithm?
• Approximating connectivity domination in weighted bounded-genus graphs

Cited In (6)

• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Approximating \(k\)-connected \(m\)-dominating sets
• Algorithm and hardness results on hop domination in graphs
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs

This page was built for publication: The \(k\)-hop connected dominating set problem: approximation and hardness

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