Linear kernels and linear-time algorithms for finding large cuts

DOI10.1007/s00453-017-0388-zzbMath1396.68056OpenAlexW2766740319WikidataQ59527637 ScholiaQ59527637MaRDI QIDQ722541

Matthias Mnich, Michael Etscheid

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0388-z

zbMATH Keywords

linear-time algorithmskernelizationmax-cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Finding Detours is Fixed-Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum balanced subgraph problem parameterized above lower bound
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Separator-based data reduction for signed graph balancing
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterizing above or below guaranteed values
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Re-describing an algorithm by Hopcroft
• Which problems have strongly exponential complexity?
• Note on maximal bisection above tight lower bound
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• The linear arrangement problem parameterized above guaranteed value
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Half-integrality, LP-branching, and FPT Algorithms
• Polynomial Kernels for {\lambda}-extendible Properties Parameterized Above the Poljak-Turz\'ik Bound
• Planar Subgraph Isomorphism Revisited
• Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Signed graphs for portfolio analysis in risk management
• Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
• Reducibility among Combinatorial Problems
• Large Independent Sets in Triangle-Free Planar Graphs
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Linear kernels and linear-time algorithms for finding large cuts