Compact grid layouts of multi-level networks

S. Muthukrishnan, Mike Paterson, Suleyman Cenk Sahinalp, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingChapter


    We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids. Besides traditional interest in these problems motivated by interconnection topologies in parallel computing and switching circuits in telecommunications, there is renewed interest in such layouts in the context of ATM (Asynchronous Transfer Mode) switches. Our results improve on the existing area bounds for these networks by factors of up to three.

    Original languageEnglish (US)
    Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
    Number of pages9
    StatePublished - 1999
    EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
    Duration: May 1 1999May 4 1999


    OtherProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99
    CityAtlanta, GA, USA

    ASJC Scopus subject areas

    • Software


    Dive into the research topics of 'Compact grid layouts of multi-level networks'. Together they form a unique fingerprint.

    Cite this