情報処理学会 第84回全国大会 会期:2022年3月3日~5日 情報処理学会 第84回全国大会 会期:2022年3月3日~5日

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.