World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES

    We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links potentially usable by this routing algorithm as it attempts to route the packet. This gives rise to a naturally defined problem, parameterized by this routing algorithm, relating to whether a packet can be routed from a given source node to a given destination node in one of our interconnection networks in which there are (possibly exponentially many) faulty links. We show that there exist such problems that are PSPACE-complete (all are solvable in PSPACE) but that there are (existing and popular) routing algorithms for which the computational complexity of the corresponding problem is significantly easier (yet still computationally intractable).

    References

    • P. Bonsma and L. Cereceda, Theoretical Computer Science 410(50), 5215 (2009), DOI: 10.1016/j.tcs.2009.08.023. Crossref, ISIGoogle Scholar
    • L. Cereceda, J. van den Heuvel and M. Johnson, Journal of Graph Theory 67(1), 69 (2011), DOI: 10.1002/jgt.20514. Crossref, ISIGoogle Scholar
    • W. J.   Dally and B.   Towles , Principles and Practices of Interconnection Networks ( Morgan Kaufmann , San Francisco , 2004 ) . Google Scholar
    • E. D. Demaine and S. Srinivas, International Journal of Computer Systems Science and Engineering 12(6), 359 (1997). ISIGoogle Scholar
    • C. J. Glass and L. M. Ni, The turn model for adaptive routing, Proc. of 19th Ann. Int. Symp, on Computer Architecture (ISCA '92) (ACM Press, 1992) pp. 278–287. Google Scholar