A TDI system and its application to approximation algorithms

Author

Cai, Mao-cheng ; Deng, Xiaotie ; Wenan Zang

Author_Institution

Inst. of Syst. Sci., Acad. Sinica, Beijing, China

fYear

1998

fDate

8-11 Nov 1998

Firstpage

227

Lastpage

231

Abstract

We 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 J. Edmonds and R. Giles (1994) 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

Keywords

computational geometry; directed graphs; TDI system; approximation algorithms; cycle packing problem; directed cycles; feedback vertex set problem; min-max relation; necessary and sufficient condition; strongly polynomial time algorithms; totally dual integral system; tournaments; Application software; Approximation algorithms; Computer science; Feedback; Manufacturing systems; Mathematics; Operating systems; Polynomials; System recovery; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on

Conference_Location

Palo Alto, CA

ISSN

0272-5428

Print_ISBN

0-8186-9172-7

Type

conf

DOI

10.1109/SFCS.1998.743448

Filename

743448