Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
DOI10.1007/978-3-319-30139-6_20zbMATH Open1475.68242OpenAlexW2491529644MaRDI QIDQ2803828FDOQ2803828
Authors: 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
Recommendations
- Distributed algorithms for \textsc{Edge Dominating Sets}
- A simple local 3-approximation algorithm for vertex cover
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- On matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 3-edge dominating set problem
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)
Cites Work
- Approximation algorithms for NP-complete problems on planar graphs
- On two techniques of combining branching and treewidth
- Locality in Distributed Graph Algorithms
- Edge Dominating Sets in Graphs
- Minimum Edge Dominating Sets
- Title not available (Why is that?)
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- New parameterized algorithms for the edge dominating set problem
- Vertex and edge covers with clustering properties: Complexity and algorithms
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Linear time algorithms for generalized edge dominating set problems
- Enumerate and measure: improving parameter budget management
- Survey of local algorithms
- Title not available (Why is that?)
- The curse of connectivity: \(t\)-total vertex (edge) cover
- Lower bounds for local approximation
- A simple local 3-approximation algorithm for vertex cover
- Distributed algorithms for edge dominating sets
- On min-max \(r\)-gatherings
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Approximation hardness of edge dominating set problems
- Approximating edge dominating set in dense graphs
- Approximability of the capacitated \(b\)-edge dominating set problem
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
Cited In (1)
This page was built for publication: Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2803828)
