QQ客服 官方微博 反馈留言

	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.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。