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

Let image be an image-vertex graph with edge weights image. We propose an algorithm computing all partitions of image into mincuts of image such that the mincuts in the partitions cannot be partitioned further into mincuts. There are image such finest mincut partitions. A mincut is a non-empty proper subset of image 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.