An exact algorithm for MAX-CUT in sparse graphs

DOI10.1016/j.orl.2006.04.001zbMath1163.90767OpenAlexW2039389937MaRDI QIDQ2467485

Vangelis Th. Paschos, Frederico 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

zbMATH Keywords

MAX-CUTexact algorithmsparse graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (6)

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree ⋮ Complement, Complexity, and Symmetric Representation ⋮ Super-polynomial approximation branching algorithms ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ New exact algorithms for the 2-constraint satisfaction problem ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP

Cites Work

• Unnamed Item
• Unnamed Item
• Three short proofs in graph theory
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A note on greedy algorithms for the maximum weighted independent set problem
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Parameterized and Exact Computation
• Node-and edge-deletion NP-complete problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: An exact algorithm for MAX-CUT in sparse graphs