ON THE COMPLEXITY OF OPTIMAL BUSED INTERCONNECTIONS

Authors
KULASINGHE P ELAMAWY A
Citation
P. Kulasinghe et A. Elamawy, ON THE COMPLEXITY OF OPTIMAL BUSED INTERCONNECTIONS, I.E.E.E. transactions on computers, 44(10), 1995, pp. 1248-1251
Citations number
9
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
Journal title
I.E.E.E. transactions on computers → ACNP
ISSN journal
00189340
Volume
44
Issue
10
Year of publication
1995
Pages
1248 - 1251
Database
ISI
SICI code
0018-9340(1995)44:10<1248:OTCOOB>2.0.ZU;2-K
Abstract
This paper addresses the combinatorial problem of constructing a minim al cost, bused, interconnection among a set of modules (Or processors) . Although some work has been reported on bused interconnection betwee n modules, the compuational complexity of the problem has not Peen pre viously addressed. We show that the optimization problem of finding a minimal cost interconnection among modules to realize a certain set of data transfers is NP-Hard.