An extended 1-D assignment problem: net assignment in gate matrix layout

Autor:	Yun-Kang Chen, Dong-Min Xu, Ernest S. Kuh
Rok vydání:	2002
Předmět:	Linear bottleneck assignment problem Discrete mathematics Matrix (mathematics) Computer science Quadratic assignment problem Heuristic (computer science) Bounded function Logic gate Hardware_INTEGRATEDCIRCUITS Net (mathematics) Assignment problem Algorithm Time complexity
Zdroj:	IEEE International Symposium on Circuits and Systems.
DOI:	10.1109/iscas.1990.111937
Popis:	A formulation for the net assignment problem in gate matrix layout is presented. A problem called the extended one-dimensional assignment problem is defined. A heuristic algorithm for solving this extended one-dimensional assignment problem is proposed. Since the net assignment problem in gate matrix is the extended one-dimensional assignment problem exactly, this algorithm is applied to the net assignment. The time complexity of the algorithm is bounded by O(m*n/sup 2/), where n is the number of nets and m is the sum of the number of vertical diffusion runs and the number of gates. >
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::7ca4c71bd6dc4830a671425f51223562 https://doi.org/10.1109/iscas.1990.111937 Zobrazit plný text záznamu