| Title | On computational complexity of a detailed routing problem in two dimensional FPGAs |
| Publication Type | Conference Paper |
| Year of Publication | 1994 |
| Authors | Wu, Y-L, Tsukiyama, S, Marek-Sadowska, M |
| Conference Name | VLSI, 1994. Design Automation of High Performance VLSI Systems. GLSV '94, Proceedings., Fourth Great Lakes Symposium on |
| Date Published | mar |
| Keywords | arbitrary fixed switch box topology, circuit layout CAD, computational complexity, connection flexibility, doglegs, global route mapping, logic arrays, logic CAD, network routing, network topology, NP-complete problem, routing problem, two dimensional FPGAs, Xilinx-4000-like routing architecture |
| Abstract | In this paper, we consider the problem of mapping a given global route to a detailed route for two dimensional homogeneous FPGAs. It has been shown that this problem is NP-complete on a popular Xilinx-4000-like routing architecture. Here, we further prove that this problem remains NP-complete for an arbitrary fixed switch box topology of the same connection flexibility, with or without doglegs allowed in detailed routes |
| DOI | 10.1109/GLSV.1994.289993 |
