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
Cai, MaochengDeng, XiaotieZang, Wenan
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
0272-5428
2020 SCImago Journal Rankings: 2.051

 

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