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.68286OpenAlexW2197735073MaRDI 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

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (5)

On approximating (connected) 2-edge dominating set by a tree ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem

This page was built for publication: On Matchings and b-Edge Dominating Sets: A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem