Approximating Bounded Degree Deletion via Matroid Matching
Approximating Bounded Degree Deletion via Matroid Matching
复制标题
DOI：
10.1007/978-3-319-57586-5_20
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Toshihiro Fujito
中科院分区：
文献类型：
--
作者：
Toshihiro Fujito
度界有界度删除问题是计算图中一个最小代价顶点集的问题，当它从图G中移除时，任何剩余顶点的度不大于b(V)。将证明b-BDD可以在范围内逼近，改进了以前的最优界，其中是最大度界，即。新的界是通过将b-BDD转化为图的边集上的2-多面体的顶点删除问题，然后将其归结为子模集合覆盖问题而得到的。
TheBounded Degree Deletionproblem with degree bound(denotedb-BDD), is that of computing a minimum cost vertex set in a graphsuch that, when it is removed fromG, the degree of any remaining vertexvis no larger thanb(v). It will be shown thatb-BDD can be approximated within, improving the previous best bound for, whereis the maximum degree bound, i.e.,. The new bound is attained by castingb-BDD as the vertex deletion problem for such a property inducing a 2-polymatroid on the edge set of a graph, and then reducing it to the submodular set cover problem.