-
63浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A Min-Max Theorem on Tournaments
SIAM Journal on Computing,-0001,37(3):923–937 | https://doi.org/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. Read More: https://epubs.siam.org/action/showAbstract?page=923&volume=37&issue=3&journalCode=smjcat
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果