Circular convex bipartite graphs: Feedback vertex set | |
Lu, Zhao ; Lu, Min ; Liu, Tian ; Xu, Ke | |
2013 | |
英文摘要 | A feedback vertex set is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is tractable for convex bipartite graphs, but NP-complete even for unweighted bipartite graphs. In a circular convex (convex, respectively) bipartite graph, there is a circular (linear, respectively) ordering defined on one class of vertices, such that for every vertex in another class, the neighborhood of this vertex is a circular arc (an interval, respectively). The minimum weighted feedback vertex set problem is shown tractable for circular convex bipartite graphs in this paper, by making a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs. ? Springer International Publishing 2013.; EI; 0 |
语种 | 英语 |
DOI标识 | 10.1007/978-3-319-03780-6_24 |
内容类型 | 其他 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/262963] |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | Lu, Zhao,Lu, Min,Liu, Tian,et al. Circular convex bipartite graphs: Feedback vertex set. 2013-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论