Generating partitions of a graph into a fixed number of minimum weight cuts

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

zbMATH Keywords

traveling salesman problemgraph partitioningcactusmincut

Mathematics Subject Classification ID

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 (4)

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

• TSPLIB
• Concorde
• PORTA

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.

This page was built for publication: Generating partitions of a graph into a fixed number of minimum weight cuts