The \(k\)-hop connected dominating set problem: approximation and hardness
type: Item
instance of: scholarly article
title: The \(k\)-hop connected dominating set problem: approximation and hardness
zbMATH Open document ID: 1384.90081
author: Rafael S. Coelho
author: Phablo F. S. Moura
author: Yoshiko Wakabayashi
published in: Journal of Combinatorial Optimization
publication date: 2017-11-09T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6804416
zbMATH Keywords: approximation algorithms
zbMATH Keywords: hardness
zbMATH Keywords: \(k\)-hop connected dominating set
zbMATH Keywords: \(k\)-disruptive separator
MaRDI profile type: Publication
full work available at URL: s10878-017-0128-y
OpenAlex ID: W2600384081
cites work: Minimal separators in \(P_4\)-sparse graphs
cites work: Connected domination and Steiner set on weighted permutation graphs
cites work: Q4258216
cites work: Q4944976
cites work: Q5692521
cites work: Max-leaves spanning tree is APX-hard for cubic graphs
cites work: A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
cites work: Optimal dynamic program for r-domination problems over tree decompositions
cites work: A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
cites work: Graph Classes: A Survey
cites work: A linear time algorithm to list the minimal separators of chordal graphs
cites work: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
cites work: Algorithms – ESA 2004
cites work: Approximation hardness of dominating set problems in bounded degree graphs
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: The \(k\)-hop connected dominating set problem: hardness and polyhedra
cites work: Approximating connectivity domination in weighted bounded-genus graphs
cites work: Permutation graphs: Connected domination and Steiner trees
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: On the hardness of approximating minimum vertex cover
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: Connected dominating set. Theory and applications
cites work: Q3579442
cites work: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
cites work: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
cites work: Vertex and edge covers with clustering properties: Complexity and algorithms
cites work: A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
cites work: Algorithmic graph theory and perfect graphs
cites work: Approximation algorithms for connected dominating sets
cites work: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
cites work: Generalized split graphs and Ramsey numbers
cites work: Approximation and intractability results for the maximum cut problem and its variants
cites work: Q4368728
cites work: Q5503435
cites work: Weighted connected domination and Steiner trees in distance-hereditary graphs
cites work: Enumeration of Minimal Dominating Sets and Variants
cites work: Q4636441
cites work: Listing all Minimal Separators of a Graph
cites work: Hardness of r-dominating set on Graphs of Diameter (r + 1)
cites work: Doubly chordal graphs, steiner trees, and connected domination
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
cites work: Approximation and Online Algorithms
cites work: A unified approach to domination problems on interval graphs
cites work: A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
cites work: A greedy approximation for minimum connected dominating sets
cites work: Steiner trees, connected domination and strongly chordal graphs
cites work: A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
DOI: 10.1007/S10878-017-0128-Y
description: scientific article; zbMATH DE number 6804416