An improved kernel for max-bisection above tight lower bound
DOI10.1016/J.TCS.2018.06.027zbMATH Open1440.68136OpenAlexW2809259324WikidataQ129624179 ScholiaQ129624179MaRDI QIDQ1985605FDOQ1985605
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
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
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)
Cites Work
- Matching theory
- Paths, Trees, and Flowers
- Parameterized algorithms
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some Extremal Properties of Bipartite Subgraphs
- A .699-approximation algorithm for Max-Bisection.
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Parameterized computational complexity of Dodgson and Young elections
- The RPR2 rounding technique for semidefinite programs
- Note on maximal bisection above tight lower bound
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Bisections above Tight Lower Bounds
- A 2-approximation for the maximum satisfying bisection problem
- A note on approximating Max-Bisection on regular graphs
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Linear kernels and linear-time algorithms for finding large cuts
- Approximating maximum agreement forest on multiple binary trees
- Title not available (Why is that?)
- Dealing with several parameterized problems by random methods
- Parameterized algorithms for edge biclique and related problems
- Balanced judicious bipartition is fixed-parameter tractable
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
- Title not available (Why is that?)
- 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)
