Simpler parameterized algorithm for OCT

DOI10.1007/978-3-642-10217-2_37MaRDI QIDQ3651564zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar

Publication date 11 December 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10217-2_37

zbMATH Keywords

iterative compression algorithmodd cycle transversal problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38)

Recommendations

• Subexponential parameterized odd cycle transversal on planar graphs
• Hitting selected (odd) cycles
• Finding odd cycle transversals.
• Compression via Matroids
• Another disjoint compression algorithm for odd cycle transversal

Cited in

(13)

• Maximum bipartite subgraphs of geometric intersection graphs
• Odd cycle transversal on P₅-free graphs in polynomial time
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• An Updated Experimental Evaluation of Graph Bipartization Methods
• A note on the parameterized complexity of unordered maximum tree orientation
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Subexponential parameterized odd cycle transversal on planar graphs
• List-coloring -- parameterizing from triviality
• Another disjoint compression algorithm for odd cycle transversal
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Edge bipartization faster than \(2^k\)
• Hitting selected (odd) cycles

This page was built for publication: Simpler parameterized algorithm for OCT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3651564)