An improved kernel for max-bisection above tight lower bound
type: Item
instance of: scholarly article
title: An improved kernel for max-bisection above tight lower bound
zbMATH Open document ID: 1440.68136
author: Qilong Feng
author: Senmin Zhu
author: Jianxin Wang
published in: Theoretical Computer Science
publication date: 2020-04-07T00:00:00Z
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7187632
zbMATH Keywords: Max-Bisection
zbMATH Keywords: Gallai-Edmonds decomposition
zbMATH Keywords: kernelization
MaRDI profile type: Publication
full work available at URL: j.tcs.2018.06.027
OpenAlex ID: W2809259324
cites work: Parameterized computational complexity of Dodgson and Young elections
cites work: Approximating maximum agreement forest on multiple binary trees
cites work: Parameterized Algorithms
cites work: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
cites work: Q4393480
cites work: Paths, Trees, and Flowers
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: Q4550236
cites work: \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
cites work: Linear kernels and linear-time algorithms for finding large cuts
cites work: A note on approximating Max-Bisection on regular graphs
cites work: The RPR2 rounding technique for semidefinite programs
cites work: Dealing with several parameterized problems by random methods
cites work: Parameterized algorithms for edge biclique and related problems
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Fixed-parameter complexity in AI and nonmonotonic reasoning
cites work: Note on maximal bisection above tight lower bound
cites work: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
cites work: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
cites work: Q4654270
cites work: Balanced Judicious Bipartition is Fixed-Parameter Tractable
cites work: Matching theory
cites work: Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
cites work: Bisections above Tight Lower Bounds
cites work: A 2-approximation for the maximum satisfying bisection problem
cites work: A .699-approximation algorithm for Max-Bisection.
Wikidata QID: Q129624179
DOI: 10.1016/J.TCS.2018.06.027
Recommended article: A new kernel for parameterized Max-Bisection above tight lower bound
Recommended article: Q3499508
Recommended article: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Recommended article: Kernelization: New Upper and Lower Bound Techniques
Recommended article: Q4558957
Recommended article: Note on maximal bisection above tight lower bound
Recommended article: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Recommended article: Q4537699
Recommended article: Lower bounds on kernelization
Recommended article: Q4550236
description: scientific article; zbMATH DE number 7187632