Linear kernels and linear-time algorithms for finding large cuts
From MaRDI portal
(Redirected from Publication:722541)
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
Cites work
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- scientific article; zbMATH DE number 780784 (Why is no real title available?)
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Half-integrality, LP-branching, and FPT algorithms
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Large independent sets in triangle-free planar graphs
- Linear kernels and linear-time algorithms for finding large cuts
- Linear time parameterized algorithms for subset feedback vertex set
- Linear-Time Approximation Algorithms for the Max Cut Problem
- Maximum balanced subgraph problem parameterized above lower bound
- Note on maximal bisection above tight lower bound
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Planar subgraph isomorphism revisited
- Polynomial kernels for \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Re-describing an algorithm by Hopcroft
- Reducibility among combinatorial problems
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Separator-based data reduction for signed graph balancing
- Signed graphs for portfolio analysis in risk management
- Solving MAX-\(r\)-SAT above a tight lower bound
- Some Extremal Properties of Bipartite Subgraphs
- The linear arrangement problem parameterized above guaranteed value
- Which problems have strongly exponential complexity?
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
Cited in
(13)- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Polynomial kernels for \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Odd multiway cut in directed acyclic graphs
- Max-Cut parameterized above the Edwards-Erdős bound
- Linear kernels for separating a graph into components of bounded size
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- \textsc{Max-Cut Above Spanning Tree} is fixed-parameter tractable
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Finding detours is fixed-parameter tractable
- An improved kernel for max-bisection above tight lower bound
- Linear kernels and linear-time algorithms for finding large cuts
- scientific article; zbMATH DE number 7378605 (Why is no real title available?)
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)
