An improved kernel for max-bisection above tight lower bound

DOI10.1016/j.tcs.2018.06.027zbMath1440.68136OpenAlexW2809259324WikidataQ129624179 ScholiaQ129624179MaRDI QIDQ1985605

Qilong Feng, Jianxin Wang, Senmin Zhu

Publication date: 7 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.027

zbMATH Keywords

kernelizationGallai-Edmonds decompositionMax-Bisection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Balanced polychromatic 2-coloring of triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• A 2-approximation for the maximum satisfying bisection problem
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Linear kernels and linear-time algorithms for finding large cuts
• Approximating maximum agreement forest on multiple binary trees
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Matching theory
• A note on approximating Max-Bisection on regular graphs
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Note on maximal bisection above tight lower bound
• Parameterized computational complexity of Dodgson and Young elections
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• Dealing with several parameterized problems by random methods
• Parameterized algorithms for edge biclique and related problems
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Bisections above Tight Lower Bounds
• Paths, Trees, and Flowers
• The RPR2 rounding technique for semidefinite programs
• Parameterized Algorithms
• Some Extremal Properties of Bipartite Subgraphs
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: An improved kernel for max-bisection above tight lower bound