loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
13th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'05)
Practicable Layouts for Optimal Circulant Graphs
Lugano, Switzerland
February 09-February 12
ISBN: 0-7695-2280-7
Enrique Vallejo, University of Cantabria, Spain
Ram? Beivide, University of Cantabria, Spain
Carmen Mart?nez, University of Cantabria, Spain
Circulant graphs have been deeply studied in technical literature. Midimew networks are a class of distance-related optimal circulant graphs of degree four which have applications in network engineering and coding theory. In this research, a new layout for Midimew networks which keeps the maximum link length under the value √5 is presented, considering unitary length as the subjacent mesh link's length. The most interesting Midimew sizes are studied: dense and quasi-dense cases, with bounded link length layouts in both cases, although the proposed algorithm is also valid for other network sizes. These results improve a previously known result in a maximum factor of √5.
Also, the number of planar layers necessary to implement this layout is studied. In addition, an expandability method is presented which enables network expansion without modifying existing nodes or links, except those needed to connect to new nodes. Finally, this layout is compared to the classical folded Torus. When considering both physical and topological distances and propagation delays our proposal is clearly competitive against Tori.
Citation:
Enrique Vallejo, Ram? Beivide, Carmen Mart?nez, "Practicable Layouts for Optimal Circulant Graphs," pdp, pp.118-125, 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.