File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: TDI system and its application to approximation algorithms

TitleTDI system and its application to approximation algorithms
Authors
Issue Date1998
Citation
Annual Symposium On Foundations Of Computer Science - Proceedings, 1998, p. 227-231 How to Cite?
AbstractWe obtain a necessary and sufficient condition for tournaments to possess a 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; the condition and the algorithms are all based on a totally dual integral (TDI) system, a theoretical framework introduced by Edmonds and Giles for establishing min-max results. As a consequence, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.
Persistent Identifierhttp://hdl.handle.net/10722/158854
ISSN
2020 SCImago Journal Rankings: 2.949

 

DC FieldValueLanguage
dc.contributor.authorCai, Maochengen_US
dc.contributor.authorDeng, Xiaotieen_US
dc.contributor.authorZang, Wenanen_US
dc.date.accessioned2012-08-08T09:03:56Z-
dc.date.available2012-08-08T09:03:56Z-
dc.date.issued1998en_US
dc.identifier.citationAnnual Symposium On Foundations Of Computer Science - Proceedings, 1998, p. 227-231en_US
dc.identifier.issn0272-5428en_US
dc.identifier.urihttp://hdl.handle.net/10722/158854-
dc.description.abstractWe obtain a necessary and sufficient condition for tournaments to possess a 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; the condition and the algorithms are all based on a totally dual integral (TDI) system, a theoretical framework introduced by Edmonds and Giles for establishing min-max results. As a consequence, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.en_US
dc.languageengen_US
dc.relation.ispartofAnnual Symposium on Foundations of Computer Science - Proceedingsen_US
dc.titleTDI system and its application to approximation algorithmsen_US
dc.typeConference_Paperen_US
dc.identifier.emailZang, Wenan:wzang@maths.hku.hken_US
dc.identifier.authorityZang, Wenan=rp00839en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0032313904en_US
dc.identifier.spage227en_US
dc.identifier.epage231en_US
dc.identifier.scopusauthoridCai, Maocheng=7202863434en_US
dc.identifier.scopusauthoridDeng, Xiaotie=7401768881en_US
dc.identifier.scopusauthoridZang, Wenan=7005740804en_US
dc.identifier.issnl0272-5428-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats