On the kernelization complexity of problems on graphs without long odd cycles

DOI10.1007/978-3-642-32241-9_38zbMATH Open1295.68136OpenAlexW204959020MaRDI QIDQ2914348FDOQ2914348

Authors: Fahad Panolan, Ashutosh Rai 

Publication date: 25 September 2012

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-32241-9_38

Recommendations

• On polynomial kernels for structural parameterizations of odd cycle transversal
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• Compression via Matroids
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• On the complexity of finding large odd induced subgraphs and odd colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (3)

• Polynomial kernels for vertex cover parameterized by small degree modulators
• On the complexity of finding large odd induced subgraphs and odd colorings
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles

This page was built for publication: On the kernelization complexity of problems on graphs without long odd cycles

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