Simpler parameterized algorithm for OCT. (English) Zbl 1267.05268
Fiala, Jiří (ed.) et al., Combinatorial algorithms. 20th international workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-10216-5/pbk). Lecture Notes in Computer Science 5874, 380-384 (2009).
Summary: We give a simple and intuitive fixed parameter tractable algorithm for the odd cycle transversal problem, running in time \(O(3^{k } \cdot k \cdot |E| \cdot |V|)\). Our algorithm is best viewed as a reinterpretation of the classical iterative compression algorithm for odd cycle transversal by B. Reed et al. [Oper. Res. Lett. 32, No. 4, 299–301 (2004; Zbl 1052.05061)].
For the entire collection see [Zbl 1177.68008].
For the entire collection see [Zbl 1177.68008].
