Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
The power of reconfiguration
| |
|
Complexity (Session 4)
The power of reconfiguration
Y. Ben-Asher1 , D. Peleg2 , R. Ramaswami3 and A. Schuster1 
| (1) |
Department of Computer Science, The Hebrew University, 91904 Jerusalem, Israel |
| (2) |
Department of Applied Mathematics and Computer Science, The Weizmann Institute, 76100 Rehovot, Israel |
| (3) |
IBM T.J. Watson Research Center, P.O. Box 704, 10598 Yorktown Heights, NY, USA |
Abstract
This paper concerns the computational aspects of the reconfigurable network model. The computational power of the model is investigated under several network topologies and assuming several variants of the model. In particular, it is shown that there are reconfigurable machines based on simple network topologies, that are capable of solving large classes of problems in constant time. These classes depend on the kinds of switches assumed for the network nodes. Reconfigurable networks are also compared with various other models of parallel computation, like PRAM's and Branching Programs.
Supported in part by an Allon Fellowship, by a Bantrell Fellowship and by a Walter and Elise Haas Career Development Award.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|