An exact algorithm for MAX-CUT in sparse graphs
From MaRDI portal
Publication:2467485
DOI10.1016/J.ORL.2006.04.001zbMATH Open1163.90767OpenAlexW2039389937MaRDI QIDQ2467485FDOQ2467485
Vangelis Th. Paschos, F. Della Croce, M. J. Kamiński
Publication date: 21 January 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2006.04.001
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on greedy algorithms for the maximum weighted independent set problem
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Node-and edge-deletion NP-complete problems
- Three short proofs in graph theory
- Parameterized and Exact Computation
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Cited In (13)
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- New exact algorithms for the 2-constraint satisfaction problem
- An experimental evaluation of semidefinite programming and spectral algorithms for max cut
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Super-polynomial approximation branching algorithms
- Optimization via enumeration: A new algorithm for the max cut problem
- Complement, Complexity, and Symmetric Representation
- 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(\sqrt n)\)-approximation algorithm for directed sparsest cut
- A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
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)
