Generalization of Min-Cut Partitioning to Tree Structures
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Disclosed is a heuristic to solve a generalization of the min-cut partitioning problem. The generalized min-cut problem is that of mapping the nodes of an hypergraph G onto the vertices of a tree structure T, and the cost function to be minimized is the cost of global routing of the hyperedges of G on the edges of T. We refer to this as the Min- Cost Tree Partitioning (MCTP) problem.