Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}

DOI10.1007/s00224-018-09909-5zbMath1434.68748MaRDI QIDQ2300620

Meirav Zehavi, Saket Saurabh, Jayakrishnan Madathil

Publication date: 27 February 2020

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-018-09909-5

zbMATH Keywords

polynomial kernel; max-cut; fixed-parameter tractable algorithm; above guarantee parameterization

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68Q27: Parameterized complexity, tractability and kernelization