Approximation algorithms for partial vertex covers in trees

DOI10.1142/s0129054123500089MaRDI QIDQ6554733

Ojas Parekh, Vahan V. Mkrtchyan, K. Subramani

Publication date: 13 June 2024

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

treeapproximation algorithmvertex coverbudgeted maximum coverage problempartial vertex cover\textbf{NP-completeness}

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using homogeneous weights for approximating the partial cover problem
• Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7
• Finding kth paths and p-centers by generating and searching good data structures
• Approximation algorithms for partial covering problems
• Reducibility among Combinatorial Problems
• Applications of approximation algorithms to cooperative games
• Approximation of Partial Capacitated Vertex Cover
• Pseudorandom sets in Grassmann graph have near-perfect expansion

This page was built for publication: Approximation algorithms for partial vertex covers in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6554733)