Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
A Simplified Analysis of the Good-Bad -Approximation Algorithm for Some Minimum-Cost Graph Problems
Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade
In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected…
cs.DS2022
Partial Vertex Cover on Graphs of Bounded Degeneracy
Fahad Panolan, Hannane Yaghoubizade
In the Partial Vertex Cover (PVC) problem, we are given an -vertex graph and a positive integer , and the objective is to find a vertex subset of size maximizing…