您当前所在位置: 首页 > 学者

陈旭瑾

  • 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

URL:https://epubs.siam.org/action/showAbstract?page=923&volume=37&issue=3&journalCode=smjcat

摘要/描述

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文件,请等待学者更新

我要评论

全部评论 0

本学者其他成果

    同领域成果