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

Mathematics Subject Classification ID

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)

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

Cites Work

• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A simple local 3-approximation algorithm for vertex cover
• Approximability of the capacitated \(b\)-edge dominating set problem
• Approximating edge dominating set in dense graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation hardness of edge dominating set problems
• Distributed algorithms for \textsc{Edge Dominating Sets}
• Edge Dominating Sets in Graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Enumerate and measure: improving parameter budget management
• Linear time algorithms for generalized edge dominating set problems
• Locality in Distributed Graph Algorithms
• Minimum Edge Dominating Sets
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• New parameterized algorithms for the 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
• On min-max \(r\)-gatherings
• On two techniques of combining branching and treewidth
• Survey of local algorithms
• The curse of connectivity: \(t\)-total vertex (edge) cover
• Vertex and edge covers with clustering properties: Complexity and algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited In (2)

• A simple local 3-approximation algorithm for vertex cover
• Distributed algorithms for \textsc{Edge Dominating Sets}

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)