On approximating (connected) 2-edge dominating set by a tree

DOI10.1007/s00224-017-9764-yzbMath1390.68762MaRDI QIDQ1635808

Toshihiro Fujito, Tomoaki Shimoda

Publication date: 1 June 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9764-y

zbMATH Keywords

approximation algorithms; connected dominating sets; tree cover; \(b\)-edge domination; edge dominating sets

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