A min-max theorem on tournaments

doi:10.1137/060649987

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	A min-max theorem on tournaments
	Chen, Xujin; Hu, Xiaodong; Zang, Wenan
刊名	SIAM JOURNAL ON COMPUTING
	2007
卷号	37 期号:3 页码:923-937
关键词	min-max relation feedback vertex set tournament packing covering
ISSN号	0097-5397
DOI	10.1137/060649987
英文摘要	We present a structural characterization of all tournaments T = ( V, A) such that, for any nonnegative integral weight function defined on V, the maximum size of a feedback vertex set packing is equal to the minimum weight of a triangle in T. We also answer a question of Frank by showing that it is NP- complete to decide whether the vertex set of a given tournament can be partitioned into two feedback vertex sets. In addition, we give exact and approximation algorithms for the feedback vertex set packing problem on tournaments.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SIAM PUBLICATIONS
WOS记录号	WOS:000249690800011
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/4730]
专题	应用数学研究所
通讯作者	Chen, Xujin
作者单位	1.Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Hu, Xiaodong,Zang, Wenan. A min-max theorem on tournaments[J]. SIAM JOURNAL ON COMPUTING,2007,37(3):923-937.
APA	Chen, Xujin,Hu, Xiaodong,&Zang, Wenan.(2007).A min-max theorem on tournaments.SIAM JOURNAL ON COMPUTING,37(3),923-937.
MLA	Chen, Xujin,et al."A min-max theorem on tournaments".SIAM JOURNAL ON COMPUTING 37.3(2007):923-937.