Computing finest mincut partitions of a graph and application to routing problems

DOI10.1016/J.DAM.2007.03.022MaRDI QIDQ2473036zbMATH OpenOpenAlexFDO

Authors Dirk Oliver Theis, Klaus M. Wenger, Gerhard Reinelt

Publication date 26 February 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.03.022

zbMATH Keywords

clusteringcactusminimum cutrouting problemfinest partition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Recommendations

• Generating partitions of a graph into a fixed number of minimum weight cuts
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 3891429
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• scientific article; zbMATH DE number 1372653

Cites work

• scientific article; zbMATH DE number 2134197 (Why is no real title available?)
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• scientific article; zbMATH DE number 1568940 (Why is no real title available?)
• scientific article; zbMATH DE number 1568941 (Why is no real title available?)
• scientific article; zbMATH DE number 6472607 (Why is no real title available?)
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A branch-and-cut algorithm for the undirected rural postman problem
• A cutting plane algorithm for the general routing problem
• A fast algorithm for cactus representations of minimum cuts
• A fundamental problem in vehicle routing
• A new approach to the minimum cut problem
• A polyhedral approach to the rural postman problem
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• Canonical cactus representation for miminum cuts
• Facet identification for the symmetric traveling salesman polytope
• Generating partitions of a graph into a fixed number of minimum weight cuts
• On general routing problems
• Practical performance of efficient minimum cut algorithms
• The general routing polyhedron: A unifying framework
• The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• The traveling salesman problem and its variations
• The traveling salesman. Computational solutions for RSP applications

Cited in

(4)

• A heuristic method for solving the problem of partitioning graphs with supply and demand
• Partitioning of supply/demand graphs with capacity limitations: an ant colony approach
• Generating partitions of a graph into a fixed number of minimum weight cuts
• On approximate data reduction for the Rural Postman Problem: Theory and experiments

Describes a project that uses

Uses Software

• SMAPO
• PORTA
• TSPLIB

This page was built for publication: Computing finest mincut partitions of a graph and application to routing problems

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