Distance-hereditary embeddings of circulant graphs

Author

Martínez, Carmen ; Beivide, Ramón ; Gutierrez, Jaime ; Izu, Cruz

Author_Institution

Dept. Electronica y Computadores, Cantabria Univ., Santander, Spain

fYear

2003

fDate

28-30 April 2003

Firstpage

320

Lastpage

324

Abstract

In this paper we present a distance-hereditary decomposition of optimal chordal rings of 2k² nodes into a set of rings of 2k nodes, where k is the diameter. All the rings belonging to this set have the same length and their diameter corresponds to the diameter of the chordal ring in which they are embedded. The members of this embedded set of rings are non-disjoint and preserve the minimal routing of the original circulant graph. Besides its practical consequences, our research allows the presentation of these optimal circulant graphs as a particular evolution of the traditional ring topology.

Keywords

graph theory; multiprocessor interconnection networks; network topology; distance-hereditary decomposition; distance-hereditary embeddings; minimal routing; nodes; optimal chordal rings; optimal circulant graphs; ring topology; Application software; Australia; Buildings; Computer networks; Computer science; Concurrent computing; Design optimization; Multiprocessor interconnection networks; Routing; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Technology: Coding and Computing [Computers and Communications], 2003. Proceedings. ITCC 2003. International Conference on

Print_ISBN

0-7695-1916-4

Type

conf

DOI

10.1109/ITCC.2003.1197548

Filename

1197548