Browse Prior Art Database

Generalization of Min-Cut Partitioning to Tree Structures

IP.com Disclosure Number: IPCOM000036196D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Vijayan, G [+details]

Abstract

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.