Improved approximations for tour and tree covers
From MaRDI portal
Publication:1879245
DOI10.1007/s00453-003-1071-0zbMath1138.68666OpenAlexW2174778260MaRDI QIDQ1879245
Ojas Parekh, Amitabh Sinha, Goran Konjevod, Jochen Könemann
Publication date: 22 September 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-003-1071-0
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Approximating the Minimum Tour Cover with a Compact Linear Program ⋮ Graph covering using bounded size subgraphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Approximating the minimum tour cover of a digraph ⋮ Approximation algorithms for metric tree cover and generalized tour and tree covers ⋮ A primal-dual method for approximating tree cover with two weights ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
