Approximation algorithms for minimum weight connected 3-path vertex cover

DOI10.1016/j.amc.2018.11.045zbMath1428.05297MaRDI QIDQ2008557

Ding-Zhu Du, Zhao Zhang, Xiaosong Li, Yingli Ran, Xiao-hui Huang

Publication date: 26 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2018.11.045

zbMATH Keywords

approximation algorithm; weight; non-submodular potential function; connected \(k\)-path vertex cover

Mathematics Subject Classification ID

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

05C85: Graph algorithms (graph-theoretic aspects)