On approximating (connected) 2-edge dominating set by a tree

DOI10.1007/S00224-017-9764-YzbMath1390.68762OpenAlexW2599678043MaRDI QIDQ1635808

Toshihiro Fujito, Tomoaki Shimoda

Publication date: 1 June 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9764-y

zbMATH Keywords

approximation algorithmsconnected dominating setstree cover\(b\)-edge dominationedge dominating sets

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)

Related Items (1)

EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Connected dominating set. Theory and applications
• 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
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem

This page was built for publication: On approximating (connected) 2-edge dominating set by a tree