Circular convex bipartite graphs: Feedback vertex sets

doi:10.1016/j.tcs.2014.05.001

CORC > 北京大学 > 信息科学技术学院

	Circular convex bipartite graphs: Feedback vertex sets
	Liu, Tian ; Lu, Min ; Lu, Zhao ; Xu, Ke
刊名	理论计算机科学
	2014
关键词	Feedback vertex set Circular convex bipartite graph Convex bipartite graph Cook reduction Tractability ALGORITHMS
DOI	10.1016/j.tcs.2014.05.001
英文摘要	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 staking a Cook reduction (i.e. polynomial time Turing reduction) for this problem from circular convex bipartite graphs to convex bipartite graphs. (C) 2014 Elsevier B.V. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000343784700007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Theory & Methods; SCI(E); EI; 1; ARTICLE; lt@pku.edu.cn; kexu@nlsde.buaa.edu.cn; ,SI; 55-62; 556
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/152020]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Liu, Tian,Lu, Min,Lu, Zhao,et al. Circular convex bipartite graphs: Feedback vertex sets[J]. 理论计算机科学,2014.
APA	Liu, Tian,Lu, Min,Lu, Zhao,&Xu, Ke.(2014).Circular convex bipartite graphs: Feedback vertex sets.理论计算机科学.
MLA	Liu, Tian,et al."Circular convex bipartite graphs: Feedback vertex sets".理论计算机科学 (2014).