Two-segmented channel routing is strong NP-complete
| Autor: | Wing Ning Li |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Static routing
Dynamic Source Routing Equal-cost multi-path routing Applied Mathematics DSRFLOW Path vector protocol Complexity Channel routing NP-completeness Multipath routing Problem reduction Discrete Mathematics and Combinatorics Destination-Sequenced Distance Vector routing Routing (electronic design automation) Algorithm Mathematics Segmented channel |
| Zdroj: | Discrete Applied Mathematics. 78(1-3):291-298 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/s0166-218x(97)00020-6 |
| Popis: | Two-segmented channel routing is a special case of segmented channel routing where each net connection is restricted to occupying two track segments at most. In order to achieve various performance measures in a design, such a restriction is sometimes necessary. Segmented channel routing problems come from the wiring of field programmable gate arrays (FPGAs) and are known to be NP-complete in the strong sense. However, whether the special case 2-segmented channel routing remains NP-complete in the strong sense or not has not been proved. In this paper, we show that the 2-segmented channel routing problem remains strongly NP-complete, and thus an efficient optimal algorithm for this special case of the segmented channel routing problem is unfortunately unlikely to exist. Our technique holds also for the case where connection lengths are bounded and settles an open question raised in Gamal et al. (1991), Li (1995), and Roychowdhury (1993). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect