From Graph Orientation to the Unweighted Maximum Cut

DOI10.1007/978-3-319-42634-1_30MaRDI QIDQ2817879zbMATH OpenOpenAlexFDO

Authors Walid Ben-Ameur, Antoine Glorieux, José Neto

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-42634-1_30

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Mixed integer programming (90C11)

Recommendations

• Max-cut under graph constraints
• Approximating graph-constrained max-cut
• Unifying maximum cut and minimum cut of a planar graph
• Maximum directed cuts in graphs with degree constraints
• An approximate algorithm for the solution of the problem of finding the maximum weighted cut of a graph
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• On the approximability of Max-Cut
• scientific article; zbMATH DE number 1187148
• Unbalanced graph cuts with minimum capacity

Cites work

• scientific article; zbMATH DE number 1232919 (Why is no real title available?)
• scientific article; zbMATH DE number 2196287 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A gradient-based randomised heuristic for the maximum cut problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Geometry of cuts and metrics
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• On the cut polytope
• P-Complete Approximation Problems
• Randomized heuristics for the Max-Cut problem
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Some optimal inapproximability results
• Spectral bounds for the maximum cut problem
• Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• The maximum cut problem
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• Using domain decomposition to find graph bisectors
• Weakly bipartite graphs and the max-cut problem

Cited in

(2)

• New quadratic models for the maximum weighted cut problem
• Unbalanced graph cuts with minimum capacity

Describes a project that uses

Uses Software

• Biq Mac

This page was built for publication: From Graph Orientation to the Unweighted Maximum Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817879)