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.
My Menu
Saved Items

Complexity (Session 4)

The power of reconfiguration

Y. Ben-AsherContact Information, D. PelegContact Information, R. RamaswamiContact Information and A. SchusterContact Information

(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)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)