A min-max relation on packing feedback vertex sets

doi:10.1287/moor.1060.0200

CSpace > 应用数学研究所

	A min-max relation on packing feedback vertex sets
	Chen, Xujin; Ding, Guoli ; Hu, Xiaodong; Zang, Wenan
	2006-11-01
发表期刊	MATHEMATICS OF OPERATIONS RESEARCH
ISSN	0364-765X
卷号	31 期号:4 页码:777-788
摘要	Let G be a graph with a nonnegative integral function w defined on V(G). A collection T of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of 3 from G leaves a forest, and every vertex v is an element of V(G) is contained in at most w(v) members of F. The weight of a cycle C in G is the sum of w(v), over all vertices v of C. The purpose of this paper is to characterize all graphs with the property that, for any nonnegative integral function w, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle.
关键词	min-max relation feedback vertex set clutter packing covering
DOI	10.1287/moor.1060.0200
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000243230800008
出版者	INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1162
专题	应用数学研究所
通讯作者	Chen, Xujin
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA 3.Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Chen, Xujin,Ding, Guoli,Hu, Xiaodong,et al. A min-max relation on packing feedback vertex sets[J]. MATHEMATICS OF OPERATIONS RESEARCH,2006,31(4):777-788.
APA	Chen, Xujin,Ding, Guoli,Hu, Xiaodong,&Zang, Wenan.(2006).A min-max relation on packing feedback vertex sets.MATHEMATICS OF OPERATIONS RESEARCH,31(4),777-788.
MLA	Chen, Xujin,et al."A min-max relation on packing feedback vertex sets".MATHEMATICS OF OPERATIONS RESEARCH 31.4(2006):777-788.