Partitioning logic on graph structures to minimize routing cost

The problem of partitioning logic onto the vertices of a partition graph G such that the cost of routing the global nets of the partition on the edges of G is minimized is discussed. This is referred to as the min-cost partitioning on a graph (MCPG) problem. The MCPG problem generalizes previously studied partitioning problems, such as classical min-cut, the quadrisection approach, min-cost tree partitioning, and multiple way network partitioning. Some applications of this partitioning model are discussed, a framework for its solution is described, and experimental results are presented