\((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel

DOI10.1007/s00453-018-0418-5zbMath1406.90122OpenAlexW2783934758MaRDI QIDQ1799226

Saket Saurabh, Meirav Zehavi

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0418-5

zbMATH Keywords

kernelparameterized algorithm\textsc{Max-Cut}bounded search tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Maximum balanced subgraph problem parameterized above lower bound
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Optimization, approximation, and complexity classes
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Parameterized algorithms for graph partitioning problems
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Parameterized Algorithms

This page was built for publication: \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel