File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An approximation algorithm for feedback vertex sets in tournaments

TitleAn approximation algorithm for feedback vertex sets in tournaments
Authors
Cai, MCDeng, XZang, W
KeywordsApproximation algorithm
Feedback vertex set
Min-max relation
Tournament
Issue Date2001
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, 2001, v. 30 n. 6, p. 1993-2007 How to Cite?
DOI: http://dx.doi.org/10.1137/S0097539798338163
AbstractWe obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.
Persistent Identifierhttp://hdl.handle.net/10722/42995
ISSN
0097-5397
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 2.143
ISI Accession Number ID
WOS:000169070000012
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorCai, MCen_HK
dc.contributor.authorDeng, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2007-03-23T04:36:28Z-
dc.date.available2007-03-23T04:36:28Z-
dc.date.issued2001en_HK
dc.identifier.citationSIAM Journal On Computing, 2001, v. 30 n. 6, p. 1993-2007en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/42995-
dc.description.abstractWe obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.en_HK
dc.format.extent202651 bytes-
dc.format.extent25600 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
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© 2001 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 30, issue 6, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectApproximation algorithmen_HK
dc.subjectFeedback vertex seten_HK
dc.subjectMin-max relationen_HK
dc.subjectTournamenten_HK
dc.titleAn approximation algorithm for feedback vertex sets in tournamentsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=30&issue=6&spage=1993&epage=2007&date=2001&atitle=An+Approximation+Algorithm+for+Feedback+Vertex+Sets+in+Tournamentsen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0097539798338163en_HK
dc.identifier.scopuseid_2-s2.0-0035705954en_HK
dc.identifier.hkuros63196-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0035705954&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume30en_HK
dc.identifier.issue6en_HK
dc.identifier.spage1993en_HK
dc.identifier.epage2007en_HK
dc.identifier.isiWOS:000169070000012-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridCai, MC=7202863434en_HK
dc.identifier.scopusauthoridDeng, X=7401768881en_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