On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem

DOI10.1007/978-3-030-92702-8_5OpenAlexW4206446654MaRDI QIDQ2085737

Toshihiro Fujito, Takumi Tatematsu

Publication date: 19 October 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-92702-8_5

zbMATH Keywords

LP relaxation\(b\)-edge dominating set problem\(b\)-matchings

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Approximating edge dominating set in dense graphs
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Minimum-cost \(b\)-edge dominating sets on trees
• Approximation hardness of edge dominating set problems
• Erratum to: ``Linear time algorithms for generalized edge dominating set problems
• Approximability of the capacitated \(b\)-edge dominating set problem
• Linear time algorithms for generalized edge dominating set problems
• Minimum Edge Dominating Sets
• On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem
• Edge Dominating Sets in Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem