Partitioning planar graphs: a fast combinatorial approach for max-cut
From MaRDI portal
Publication:434180
DOI10.1007/s10589-010-9335-5zbMath1245.90107OpenAlexW2059227596MaRDI QIDQ434180
Publication date: 10 July 2012
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: http://e-archive.informatik.uni-koeln.de/605/2/zaik2010-605.pdf
Related Items
Introduction to QUBO, Complexity and Polynomially Solvable Special Cases of QUBO, Quantum Annealing versus Digital Computing, Maximum Cut Parameterized by Crossing Number, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
Uses Software
Cites Work
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Blossom V: A new implementation of a minimum cost perfect matching algorithm
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Easy and difficult objective functions for max cut
- The cut polytope and the Boolean quadric polytope
- Via Minimization with Pin Preassignments and Layer Preference
- Maximal Flow Through a Network
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- TSPLIB—A Traveling Salesman Problem Library
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Comments on F. Hadlock’s Paper: “Finding a Maximum Cut of a Planar Graph in Polynomial Time”
- A simple min-cut algorithm
- Computing Minimum-Weight Perfect Matchings
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
