Computing finest mincut partitions of a graph and application to routing problems |
| |
Authors: | Gerhard Reinelt Klaus Michael Wenger |
| |
Institution: | University of Heidelberg, Institute of Computer Science, Discrete Optimization Research Group, Im Neuenheimer Feld 368, D-69120 Heidelberg, Germany |
| |
Abstract: | Let G=(V,E,w) be an n-vertex graph with edge weights w>0. We propose an algorithm computing all partitions of V into mincuts of G such that the mincuts in the partitions cannot be partitioned further into mincuts. There are O(n) such finest mincut partitions. A mincut is a non-empty proper subset of V such that the total weight of edges with exactly one end in the subset is minimal. The proposed algorithm exploits the cactus representation of mincuts and has the same time complexity as cactus construction. An application to the exact solution of the general routing problem is described. |
| |
Keywords: | Minimum cut Finest partition Clustering Cactus Routing problem |
本文献已被 ScienceDirect 等数据库收录! |