From Graph Orientation to the Unweighted Maximum Cut
DOI10.1007/978-3-319-42634-1_30zbMATH Open1476.68192OpenAlexW2492335092MaRDI QIDQ2817879FDOQ2817879
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
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
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Mixed integer programming (90C11)
Cites Work
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Title not available (Why is that?)
- Some optimal inapproximability results
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
- On the cut polytope
- P-Complete Approximation Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Geometry of cuts and metrics
- Randomized heuristics for the Max-Cut problem
- Weakly bipartite graphs and the max-cut problem
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
- Using domain decomposition to find graph bisectors
- 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
- Title not available (Why is that?)
- Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
- The maximum cut problem
- A gradient-based randomised heuristic for the maximum cut problem
Cited In (2)
Uses Software
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)
