Feedback vertex sets on restricted bipartite graphs

doi:10.1016/j.tcs.2012.12.021

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

	Feedback vertex sets on restricted bipartite graphs
	Jiang, Wei ; Liu, Tian ; Wang, Chaoyi ; Xu, Ke
刊名	理论计算机科学
	2013
关键词	Feedback vertex set Tree convex bipartite Polynomial time N P-complete APPROXIMATION ALGORITHMS ROTATOR GRAPHS BUTTERFLIES HYPERGRAPHS MESHES BOUNDS
DOI	10.1016/j.tcs.2012.12.021
英文摘要	A feedback vertex set (FVS) in a graph is a subset of vertices whose complement induces a forest. Finding a minimum FVS is N P-complete on bipartite graphs, but tractable on convex bipartite graphs and on chordal bipartite graphs. A bipartite graph is called tree convex, if a tree is defined on one part of the vertices, such that for every vertex in the other part, its neighborhood induces a subtree. When the tree is a path, a triad or a star, the bipartite graph is called convex bipartite, triad convex bipartite or star convex bipartite, respectively. We show that: (I) FVS is tractable on triad convex bipartite graphs; (2) FVS is N P-complete on star convex bipartite graphs and on tree convex bipartite graphs where the maximum degree of vertices on the tree is at most three. (C) 2012 Elsevier B.V. All rights reserved.; http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000326061800005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=8e1609b174ce4e31116a60747a720701 ; Computer Science, Theory & Methods; SCI(E); EI; 8; ARTICLE; 41-51; 507
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/152243]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Jiang, Wei,Liu, Tian,Wang, Chaoyi,et al. Feedback vertex sets on restricted bipartite graphs[J]. 理论计算机科学,2013.
APA	Jiang, Wei,Liu, Tian,Wang, Chaoyi,&Xu, Ke.(2013).Feedback vertex sets on restricted bipartite graphs.理论计算机科学.
MLA	Jiang, Wei,et al."Feedback vertex sets on restricted bipartite graphs".理论计算机科学 (2013).