File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A min-max theorem on tournaments

TitleA min-max theorem on tournaments
Authors
Chen, XHu, XZang, W
KeywordsCovering
Feedback vertex set
Min-max relation
Packing
Tournament
Issue Date2007
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
SIAM Journal On Computing, 2007, v. 37 n. 3, p. 923-937 How to Cite?
DOI: http://dx.doi.org/10.1137/060649987
AbstractWe 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 N P-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. ©2007 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/75153
ISSN
0097-5397
2021 Impact Factor: 1.475
2020 SCImago Journal Rankings: 1.533
ISI Accession Number ID
WOS:000249690800011
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_HK
dc.contributor.authorHu, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:08:26Z-
dc.date.available2010-09-06T07:08:26Z-
dc.date.issued2007en_HK
dc.identifier.citationSIAM Journal On Computing, 2007, v. 37 n. 3, p. 923-937en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75153-
dc.description.abstractWe 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 N P-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. ©2007 Society for Industrial and Applied Mathematics.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rights© 2007 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 37, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectCoveringen_HK
dc.subjectFeedback vertex seten_HK
dc.subjectMin-max relationen_HK
dc.subjectPackingen_HK
dc.subjectTournamenten_HK
dc.titleA min-max theorem on tournamentsen_HK
dc.typeArticleen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/060649987en_HK
dc.identifier.scopuseid_2-s2.0-46449129704en_HK
dc.identifier.hkuros143669en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-46449129704&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume37en_HK
dc.identifier.issue3en_HK
dc.identifier.spage923en_HK
dc.identifier.epage937en_HK
dc.identifier.eissn1095-7111-
dc.identifier.isiWOS:000249690800011-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChen, X=8987182300en_HK
dc.identifier.scopusauthoridHu, X=21934107100en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats