Linear Kernels and Linear-Time Algorithms for Finding Large Cuts

DOI10.4230/LIPIcs.ISAAC.2016.31zbMath1398.68229OpenAlexW2576432037MaRDI QIDQ4636514

Matthias Mnich, Michael Etscheid

Publication date: 19 April 2018

Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2016.31

zbMATH Keywords

fixed-parameter tractabilitykernelizationmax-cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree} ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators

This page was built for publication: Linear Kernels and Linear-Time Algorithms for Finding Large Cuts