期刊
DISCRETE APPLIED MATHEMATICS
卷 159, 期 17, 页码 1933-1946出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2011.06.023
关键词
Most vital vertices; Independent set; Vertex cover; Time complexity; NP-hard; Bipartite graph; Bounded treewidth; Cograph
资金
- Hungarian Scientific Research Fund, OTKA [81493]
Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too. (C) 2011 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据