\textsc{Max-Cut} parameterized above the Edwards-Erdős bound

DOI10.1007/s00453-014-9870-zzbMath1328.68086arXiv1112.3506OpenAlexW2799037470MaRDI QIDQ494801

Yong-Cai Geng, Sumit K. Garg

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilityalgorithms and data structurescombinatorial boundsmaximum cuts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Perfect forests in graphs and their extensions ⋮ Complexity of maximum cut on interval graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Algorithms for \((n,3)\)-MAXSAT and parameterization above the all-true assignment ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree} ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized complexity of multi-node hubs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized graph separation problems
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Distance-hereditary graphs
• The size of the largest bipartite subgraphs
• Note on maximal bisection above tight lower bound
• On the existence of subexponential parameterized algorithms
• On some extremal problems in graph theory
• Parametrized complexity theory.
• Max-Cut Parameterized above the Edwards-Erdős Bound
• Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
• Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Maximum Balanced Subgraph Problem Parameterized above Lower Bound
• Reducibility among Combinatorial Problems
• Bisections above Tight Lower Bounds
• Approximation and intractability results for the maximum cut problem and its variants
• Some Extremal Properties of Bipartite Subgraphs
• On the complexity of \(k\)-SAT

This page was built for publication: \textsc{Max-Cut} parameterized above the Edwards-Erdős bound