On approximating (connected) 2-edge dominating set by a tree
type: Item
instance of: scholarly article
title: On approximating (connected) 2-edge dominating set by a tree
zbMATH Open document ID: 1390.68762
author: Toshihiro Fujito
author: Tomoaki Shimoda
published in: Theory of Computing Systems
publication date: 2018-06-01T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6879941
zbMATH Keywords: edge dominating sets
zbMATH Keywords: approximation algorithms
zbMATH Keywords: tree cover
zbMATH Keywords: connected dominating sets
zbMATH Keywords: \(b\)-edge domination
MaRDI profile type: Publication
full work available at URL: s00224-017-9764-y
OpenAlex ID: W2599678043
cites work: Experiments on data reduction for optimal domination in networks
cites work: Approximating the tree and tour covers of a graph
cites work: On min-max \(r\)-gatherings
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Approximability of the capacitated \(b\)-edge dominating set problem
cites work: Enumerate and Measure: Improving Parameter Budget Management
cites work: Q5692521
cites work: \(k\)-domination and \(k\)-independence in graphs: A survey
cites work: Approximation hardness of edge dominating set problems
cites work: Algorithms and Models for the Web-Graph
cites work: On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
cites work: Connected dominating set. Theory and applications
cites work: New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
cites work: edge dominating set: Efficient Enumeration-Based Exact Algorithms
cites work: The Curse of Connectivity: t-Total Vertex (Edge) Cover
cites work: Vertex and edge covers with clustering properties: Complexity and algorithms
cites work: Q3691778
cites work: Q3691779
cites work: On two techniques of combining branching and treewidth
cites work: On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
cites work: A greedy algorithm for the fault-tolerant connected dominating set in a general graph
cites work: Q5572939
cites work: Q4368729
cites work: Q4368728
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Matching theory
cites work: Depth-first search and the vertex cover problem
cites work: Approximating edge dominating set in dense graphs
cites work: Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
cites work: A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
cites work: On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
cites work: New parameterized algorithms for the edge dominating set problem
cites work: Edge Dominating Sets in Graphs
DOI: 10.1007/S00224-017-9764-Y
Recommended article: On Approximating (Connected) 2-Edge Dominating Set by a Tree
Recommended article: Algorithm and complexity of the two disjoint connected dominating sets problem on trees
Recommended article: A polylogarithmic approximation algorithm for 2-edge-connected dominating set
Recommended article: The complexity of total edge domination and some related results on trees
Recommended article: On approximability of the independent/connected edge dominating set problems
Recommended article: Q4472438
Recommended article: Q4582712
Recommended article: Edge domination and 2-independence in trees
Recommended article: Bounds on the vertex-edge domination number of a tree
Recommended article: Approximating k-Connected m-Dominating Sets
description: scientific article; zbMATH DE number 6879941