2026-05-14T23:40:50Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00178851 2025-01-20T04:58:20Z 1164:2592:9018:9163

Approximating Bounded Degree Deletion via Matroid Matching Approximating Bounded Degree Deletion via Matroid Matching Toshihiro, Fujimoto Toshihiro, Fujimoto The Bounded Degree Deletion problem with degree bound b : V → Z+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V, E) such that, when it is removed from G, the degree of any remaining vertex v is no larger than b (v). It will be shown that b-BDD can be approximated within max {2,b / 2 ＋ 1}, improving the previous best bound for 2 ≤ b ≤ 5, where b is the maximum degree bound, i.e., b = max {b (v) The Bounded Degree Deletion problem with degree bound b : V → Z+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V, E) such that, when it is removed from G, the degree of any remaining vertex v is no larger than b (v). It will be shown that b-BDD can be approximated within max {2,b / 2 ＋ 1}, improving the previous best bound for 2 ≤ b ≤ 5, where b is the maximum degree bound, i.e., b = max {b (v) 情報処理学会 2017-05-05 eng technical report https://ipsj.ixsq.nii.ac.jp/records/178851 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2017-AL-163 9 1 7 https://ipsj.ixsq.nii.ac.jp/record/178851/files/IPSJ-AL17163009.pdf application/pdf 614.4 kB