A Sufficiency Condition for Graphs to Admit Greedy Algorithm in Solving the Minimum Sum Vertex Cover Problem
S. V. Rohith Mohan, B. Devadas Acharya, Mukti Acharya · 2011
Minimum sum vertex cover (MSVC) problem is a NP- Complete problem which arises in the context of designing efficient algorithms for solving semi- definite programs, and in the context of speeding up matrix computations. In this paper, in order to solve the MSVC problem, we address a new general problem : Precisely which graphs admit greedy algorithm in solving minimizing minimum sum vertex cover (MSVC) problem ? We obtain a sufficiency condition for solving this problem; the graphs satisfying this condition have been called recurrent dominancy regular partition graphs (R-DRPG).