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

DOI10.1016/J.DAM.2007.03.022zbMATH Open1165.90612OpenAlexW1968981133MaRDI QIDQ2473036FDOQ2473036

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

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

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)

Cites Work

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

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

Uses Software

• TSPLIB
• PORTA
• SMAPO

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)