Improved approximation algorithm for minimum weight \(k\)-subgraph cover problem

DOI10.1007/978-3-030-36412-0_28zbMath1435.68242MaRDI QIDQ2180167

Zhao Zhang, Pengcheng Liu, Xiao-hui Huang

Publication date: 13 May 2020

Full work available at URL: https://doi.org/10.1007/978-3-030-36412-0_28

zbMATH Keywords

approximation algorithm; girth; connected \(k\)-subgraph cover

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C40: Connectivity