Note on maximal bisection above tight lower bound

DOI10.1016/j.ipl.2010.08.001zbMath1379.68165arXiv1005.2848OpenAlexW1999270628MaRDI QIDQ1675768

Anders Yeo, Gregory Gutin

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1005.2848

zbMATH Keywords

algorithmskernelsfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Unnamed Item ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex cover problem parameterized above and below tight bounds
• The complexity of König subgraph problems and above-guarantee vertex cover
• Note on Max Lin-2 above average
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Betweenness parameterized above tight lower bound
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Interval Completion Is Fixed Parameter Tractable
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Approximation and intractability results for the maximum cut problem and its variants
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Some Extremal Properties of Bipartite Subgraphs