DocumentCode
2823487
Title
On a graph partitioning problem with applications to VLSI layout
Author
Sen, Arunabha ; Deng, Haiyong ; Guha, Sumanta
Author_Institution
Dept. of Comput. Sci., Arizona State Univ., Tempe, AZ, USA
fYear
1991
fDate
11-14 Jun 1991
Firstpage
2846
Abstract
A graph partitioning problem with application to VLSI layout is discussed. It has been shown that for a general graph the partitioning problem is NP-complete. It is also shown that the open problem suggested by K.J. Supowit (1987) is also NP-complete. An integer linear programming formulation for the graph partitioning problem is given. The problem can then be solved using one of the several methods for solving integer linear programming problems. A linear time algorithm for the case when the graph is a tree is given
Keywords
VLSI; circuit layout; computational complexity; graph theory; integer programming; linear programming; IC layout; NP-complete; VLSI layout; graph partitioning problem; integer linear programming; linear time algorithm; tree; Application software; Circuit optimization; Computer science; Costs; Degradation; Linear programming; Positron emission tomography; Rivers; Routing; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN
0-7803-0050-5
Type
conf
DOI
10.1109/ISCAS.1991.176137
Filename
176137
Link To Document