Generating partitions of a graph into a fixed number of minimum weight cuts
From MaRDI portal
Publication:1952501
DOI10.1016/j.disopt.2009.07.001zbMath1264.05107OpenAlexW2038523985MaRDI QIDQ1952501
Klaus M. Wenger, Gerhard Reinelt
Publication date: 31 May 2013
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2009.07.001
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Partitioning of supply/demand graphs with capacity limitations: an ant colony approach, Computing finest mincut partitions of a graph and application to routing problems, Global optimization of multilevel electricity market models including network design and graph partitioning, A heuristic method for solving the problem of partitioning graphs with supply and demand
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Facet identification for the symmetric traveling salesman polytope
- A new and improved algorithm for the 3-cut problem
- Canonical cactus representation for miminum cuts
- Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
- An improved approximation algorithm of MULTIWAY CUT.
- A faster algorithm for computing minimum 5-way and 6-way cuts in graphs
- A fast algorithm for computing minimum 3-way and 4-way cuts
- The graphical relaxation: A new framework for the symmetric traveling salesman polytope
- Implementing an efficient minimum capacity cut algorithm
- Combinatorial optimization and small polytopes
- Practical performance of efficient minimum cut algorithms
- A fast algorithm for cactus representations of minimum cuts
- A Simple Algorithm for the Planar Multiway Cut Problem
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
- An improved algorithm for the planar 3-cut problem
- An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Finding k Cuts within Twice the Optimal
- A new approach to the minimum cut problem
- On minimum 3-cuts and approximating k-cuts using Cut Trees
- Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
- Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
- A divide-and-conquer approach to the minimum \(k\)-way cut problem.
