\((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
type: Item
instance of: scholarly article
title: \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
zbMATH Open document ID: 1406.90122
author: Saket Saurabh
author: Meirav Zehavi
published in: Algorithmica
publication date: 2018-10-18T00:00:00Z
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6958251
zbMATH Keywords: \textsc{Max-Cut}
zbMATH Keywords: parameterized algorithm
zbMATH Keywords: kernel
zbMATH Keywords: bounded search tree
MaRDI profile type: Publication
full work available at URL: s00453-018-0418-5
OpenAlex ID: W2783934758
cites work: Q4263699
cites work: Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
cites work: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
cites work: Maximum balanced subgraph problem parameterized above lower bound
cites work: \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
cites work: Parameterized Algorithms
cites work: Fundamentals of parameterized complexity
cites work: Approximation algorithms for maximization problems arising in graph partitioning
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Optimization, approximation, and complexity classes
cites work: Improved fixed parameter tractable algorithms for two ``edge'' problems: MAXCUT and MAXDAG
cites work: Parameterized algorithms for graph partitioning problems
DOI: 10.1007/S00453-018-0418-5
description: scientific article; zbMATH DE number 6958251