Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
DOI10.1007/978-3-319-30139-6_20zbMath1475.68242OpenAlexW2491529644MaRDI QIDQ2803828
Toshihiro Fujito, Daichi Suzuki
Publication date: 3 May 2016
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-30139-6_20
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- New parameterized algorithms for the edge dominating set problem
- On min-max \(r\)-gatherings
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Approximating edge dominating set in dense graphs
- A simple local 3-approximation algorithm for vertex cover
- On two techniques of combining branching and treewidth
- Vertex and edge covers with clustering properties: Complexity and algorithms
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Approximation hardness of edge dominating set problems
- Approximability of the capacitated \(b\)-edge dominating set problem
- Linear time algorithms for generalized edge dominating set problems
- Survey of local algorithms
- Lower bounds for local approximation
- Enumerate and Measure: Improving Parameter Budget Management
- Minimum Edge Dominating Sets
- 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
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Edge Dominating Sets in Graphs
- Locality in Distributed Graph Algorithms
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Distributed algorithms for edge dominating sets
This page was built for publication: Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
