On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem

DOI10.1007/978-3-319-08404-6_18zbMath1417.68286MaRDI QIDQ3188895

Toshihiro Fujito

Publication date: 2 September 2014

Published in: Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08404-6_18

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms