Linear kernels and linear-time algorithms for finding large cuts
DOI10.1007/S00453-017-0388-ZzbMATH Open1396.68056DBLPjournals/algorithmica/EtscheidM18OpenAlexW2766740319WikidataQ59527637 ScholiaQ59527637MaRDI QIDQ722541FDOQ722541
Authors: Michael Etscheid, Matthias Mnich 
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
Recommendations
- Linear kernels and linear-time algorithms for finding large cuts
- Max-Cut parameterized above the Edwards-Erdős bound
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- scientific article; zbMATH DE number 6987353
- Polynomial kernels for \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Reducibility among Combinatorial Problems
- Parameterizing above or below guaranteed values
- Which problems have strongly exponential complexity?
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Half-integrality, LP-branching, and FPT algorithms
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Solving MAX-\(r\)-SAT above a tight lower bound
- Title not available (Why is that?)
- Some Extremal Properties of Bipartite Subgraphs
- The linear arrangement problem parameterized above guaranteed value
- Title not available (Why is that?)
- Large Independent Sets in Triangle-Free Planar Graphs
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Signed graphs for portfolio analysis in risk management
- Separator-based data reduction for signed graph balancing
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- Note on maximal bisection above tight lower bound
- Title not available (Why is that?)
- Planar subgraph isomorphism revisited
- 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
- Re-describing an algorithm by Hopcroft
- Linear-Time Approximation Algorithms for the Max Cut Problem
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
- 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
- Polynomial Kernels for {\lambda}-extendible Properties Parameterized Above the Poljak-Turz\'ik Bound
- Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
Cited In (7)
- An improved kernel for max-bisection above tight lower bound
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Odd Multiway Cut in Directed Acyclic Graphs
- Finding Detours is Fixed-Parameter Tractable
- Title not available (Why is that?)
- Linear kernels for separating a graph into components of bounded size
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
This page was built for publication: Linear kernels and linear-time algorithms for finding large cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722541)
