An exact algorithm for MAX-CUT in sparse graphs
From MaRDI portal
Recommendations
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
- scientific article; zbMATH DE number 1787231
- Linear-Time Approximation Algorithms for the Max Cut Problem
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Cites work
- scientific article; zbMATH DE number 1496855 (Why is no real title available?)
- scientific article; zbMATH DE number 780784 (Why is no real title available?)
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A note on greedy algorithms for the maximum weighted independent set problem
- Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
- Node-and edge-deletion NP-complete problems
- Parameterized and Exact Computation
- Three short proofs in graph theory
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
Cited in
(22)- scientific article; zbMATH DE number 4145687 (Why is no real title available?)
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- An effective compact formulation of the max cut problem on sparse graphs
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- New exact algorithms for the 2-constraint satisfaction problem
- Complement, complexity, and symmetric representation
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- Super-polynomial approximation branching algorithms
- Optimization via enumeration: A new algorithm for the max cut problem
- Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
- A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
- An O( n)-approximation algorithm for directed sparsest cut
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- A highly efficient algorithm for maximum cut on Halin graphs
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- McSparse: exact solutions of sparse maximum cut and sparse unconstrained binary quadratic optimization problems
- A combinatorial design approach to MAXCUT
This page was built for publication: An exact algorithm for MAX-CUT in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467485)
