Name
Abstract | ||
|---|---|---|
The bigraph crossing problem, embedding the two node sets of a bipartite graph G=(V0, V1, E) along two parallel lines so that edge crossings are minimized, has application to placement optimization for standard cells and other technologies. Iterative improvement heuristics involve repeated application of some transformation on an existing feasible solution to obtain better feasible solutions. Typically an increase in the number of iterations, and therefore execution time, implies an improvement in solution quality. We investigate tradeoffs between execution time and solution quality in order to establish the best heuristic for any given time budget. Our experiments show some clear trends for a scalable class of graphs based on actual circuits. These trends, based on statistically significant samples of each of several graph sizes, suggest promising directions for development of better heuristics |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/ISCAS.1999.780190 | Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium |
Keywords | Field | DocType |
VLSI,cellular arrays,circuit layout CAD,circuit optimisation,crosstalk,graph theory,integrated circuit layout,iterative methods,logic CAD,network routing,wiring,bigraph crossing minimization,execution time,iterative improvement heuristics,node sets,placement optimization,routing,scalable class,solution quality,standard cells,wire length | Graph theory,Mathematical optimization,Bigraph,Heuristic,Iterative method,Computer science,Bipartite graph,Electronic engineering,Heuristics,Parallel,Minification | Conference |
Volume | ISBN | Citations |
6 | 0-7803-5471-0 | 2 |
PageRank | References | Authors |
0.42 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias F. M. Stallmann | 1 | 166 | 19.38 |
| Franc Brglez | 2 | 525 | 80.13 |
| Debabrata Ghosh | 3 | 2 | 0.42 |