Publication
DAC 1989
Conference paper

Min-cost partitioning on a tree structure and applications

View publication

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.

Date

Publication

DAC 1989

Authors

Share