5K-03
A ZDD-Based Algorithm for Solving Minimum Weighted Vertex Cover Problems and Its Evaluation
Given an undirected vertex-weighted graph <l>G=(V,E,w)</l>, the minimum weighted vertex cover (MWVC) problem is to find a subset of vertices with every edge in the given graph having at least one of its endpoints selected such that the total weight of the subset is minimum. In this paper, we present a method using the Zero-Suppressed Binary Decision Diagram (ZDD) for solving this classic NP-hard problem, applying an efficient approximation algorithm to facilitate finding the exact solution. We show the experimental evaluation of our method compared with existing solvers including SBMS and Cliquer.