• DocumentCode
    2003157
  • Title

    Ascend/descend algorithms on Cayley graphs

  • Author

    Draper, Richard N.

  • Author_Institution
    Supercomputing Res. Center, Bowie, MD, USA
  • fYear
    1995
  • fDate
    28-31 Mar 1995
  • Firstpage
    249
  • Lastpage
    255
  • Abstract
    In a fundamental paper, F.P. Preparata and J.E. Vuillemin (1981) introduced the cube connected cycles graph and demonstrated a congestion free implementation of an ascend/descend algorithm. Subsequently, it was shown that the cube connected cycles graph is the Cayley graph of a group, the wreath product. We isolate the properties required of a Cayley graph that enable a congestion free implementation of an ascend/descend algorithm. We exhibit another family of graphs which we call supertoroids which possess this property, and we analyze the time complexity of the resulting implementation
  • Keywords
    computational complexity; graph theory; hypercube networks; Cayley graphs; ascend/descend algorithms; congestion free implementation; cube connected cycles graph; supertoroids; time complexity; wreath product; Algorithm design and analysis; Costs; Fast Fourier transforms; Multiprocessor interconnection networks; Network topology; Typesetting;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computers and Communications, 1995., Conference Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on
  • Conference_Location
    Scottsdale, AZ
  • Print_ISBN
    0-7803-2492-7
  • Type

    conf

  • DOI
    10.1109/PCCC.1995.472484
  • Filename
    472484