-
84浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A Min-Max Relation on Packing Feedback Vertex Sets
Mathematics of Operations Research,2006,31(4):649-848 | 2006年11月01日 | https://doi.org/10.1287/moor.1060.0200
Let G be a graph with a nonnegative integral function w defined on V(G). A collection ℱ of subsets of V(G) (repetition is allowed) is called a feedback vertex set packing in G if the removal of any member of ℱ from G leaves a forest, and every vertex v ∈ V(G) is contained in at most w(v) members of ℱ. 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.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果