An improved kernel for max-bisection above tight lower bound

DOI10.1016/J.TCS.2018.06.027MaRDI QIDQ1985605zbMATH OpenOpenAlexWikidataFDO

Authors Qilong Feng, Senmin Zhu, Jianxin Wang

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)

Recommendations

• A new kernel for parameterized Max-Bisection above tight lower bound
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Kernelization: new upper and lower bound techniques
• scientific article; zbMATH DE number 6987353
• Note on maximal bisection above tight lower bound
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• scientific article; zbMATH DE number 1762086
• Lower bounds on kernelization
• scientific article; zbMATH DE number 1787231

Cites work

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

Cited in

(7)

• A new kernel for parameterized Max-Bisection above tight lower bound
• Note on maximal bisection above tight lower bound
• An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• scientific article; zbMATH DE number 6987353 (Why is no real title available?)
• Balanced polychromatic 2-coloring of triangulations
• Improved kernel results for some FPT problems based on simple observations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1985605)