Min-cost partitioning on a tree structure and applications

Abstract

The authors introduce a generalization of the min-cut partitioning problem, called min-cost tree partitioning (MCTP), in which the nodes of a hypergraph G are to be mapped on the vertices of a tree structure T, and the cost function to be minimized is the cost of routing the hyperedges (i.e., the nets) of G on the edges of T. The MCTP model makes it possible to find a partition that minimizes the actual cost of doing global routing on a tree structure. The cost of global routing is simply the sum of the flow of the nets across all the cuts of the partition. The model also allows the cuts to be weighted according to their criticalities. The authors discuss an iterative improvement heuristic for solving this problem.