• DocumentCode
    1150173
  • Title

    Families of Fixed Degree Graphs for Processor Interconnection

  • Author

    Jerrum, Mark R. ; Skyum, Sven

  • Author_Institution
    Department of Computer Science, University of Edinburgh
  • Issue
    2
  • fYear
    1984
  • Firstpage
    190
  • Lastpage
    194
  • Abstract
    A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).
  • Keywords
    Graph theory; networks; parallel computation; Computer networks; Computer science; Concurrent computing; Graph theory; H infinity control; Multiprocessor interconnection networks; Parallel algorithms; Routing; Upper bound; Graph theory; networks; parallel computation;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1984.1676410
  • Filename
    1676410
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1150173