About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE TC
Paper
Generalization of Min-Cut Partitioning to Tree Structures and Its Applications
Abstract
We introduce a generalization of the min-cut partitioning problem, called Min-Cost Tree Partitioning, in which the nodes of a hypergraph G are to be mapped on to the vertices of a tree structure T, and the cost function to be minimized is the cost of routing the hyperedges of G on the edges of T. The standard min-cut problem is the simple case when the tree T is a single edge connecting two vertices. We discuss several interesting VLSI design applications for this problem. We describe an iterative improvement heuristic for this problem, in which nodes of the hypergraph are moved between the vertices of the tree. The running time of a single pass of the heuristic for the unweighted version of the problem is O(P ×D× t3), where P is the total number of pins in the hypergraph G, D is the maximum number of nodes in a hyperedge of G, and t is the number of vertices in the tree T. Several test results are also discussed. © 1991 IEEE