On Approximating (Connected) 2-Edge Dominating Set by a Tree

DOI10.1007/978-3-319-34171-2_12zbMath1386.68219OpenAlexW2505708418MaRDI QIDQ5740184

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-34171-2_12

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
New parameterized algorithms for the edge dominating set problem
A greedy algorithm for the fault-tolerant connected dominating set in a general graph
On min-max \(r\)-gatherings
\(k\)-domination and \(k\)-independence in graphs: A survey
Approximating the tree and tour covers of a graph
Approximating edge dominating set in dense graphs
Experiments on data reduction for optimal domination in networks
Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
On two techniques of combining branching and treewidth
Vertex and edge covers with clustering properties: Complexity and algorithms
Matching theory
Depth-first search and the vertex cover problem
New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
Approximation hardness of edge dominating set problems
On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
Approximability of the capacitated \(b\)-edge dominating set problem
On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
Enumerate and Measure: Improving Parameter Budget Management
On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
edge dominating set: Efficient Enumeration-Based Exact Algorithms
The Curse of Connectivity: t-Total Vertex (Edge) Cover
Edge Dominating Sets in Graphs
Approximation algorithms for NP-complete problems on planar graphs
NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
Algorithms and Models for the Web-Graph

This page was built for publication: On Approximating (Connected) 2-Edge Dominating Set by a Tree