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_5MaRDI 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

68W25: Approximation algorithms

68W27: Online algorithms; streaming algorithms