An algorithm for generating node disjoint routes in Kautz diagraphs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    35 Downloads (Pure)

    Abstract

    The authors focus on a particular class of interconnection networks: Kautz networks. These networks have nice properties: a network with degree d and N=dk+dk-1 nodes (for any cardinal d, k>0), has a diameter of at most dlog N, the degree d is fixed and independent of the network size. The network is fault-tolerant and the connectivity is d. There is a straightforward mapping from standard computation graphs such as a linear array, a ring and a tree to a Kautz network. The network allows for a simple routing algorithm, even when nodes or links are faulty. There exists d node disjoint paths between any pair of vertices. The paper presents an algorithm to generate these node disjoint routes. The routes are delivered with increasing length and are free of loops. It proves that these routes are node disjoint and as short as possible
    Original languageEnglish
    Title of host publicationFifth International Parallel Processing Symposium 1991
    Subtitle of host publicationProceedings
    Place of PublicationLos Alamitos, CA
    PublisherIEEE
    Pages102-107
    Number of pages6
    ISBN (Print)9780818691676
    DOIs
    Publication statusPublished - 1 May 1991
    Event5th International Parallel Processing Symposium 1991 - Anaheim, United States
    Duration: 30 Apr 19912 May 1991
    Conference number: 5

    Conference

    Conference5th International Parallel Processing Symposium 1991
    CountryUnited States
    CityAnaheim
    Period30/04/912/05/91

    Fingerprint Dive into the research topics of 'An algorithm for generating node disjoint routes in Kautz diagraphs'. Together they form a unique fingerprint.

    Cite this