Skip to main content

2012 | OriginalPaper | Buchkapitel

A New Hierarchical Structure of Star Graphs and Applications

verfasst von : Wei Shi, Feng Luo, Pradip Srimani

Erschienen in: Distributed Computing and Internet Technology

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

A star graph

S

n

[1], of order

n

, is defined to be a symmetric graph

G

 = (

V

,

E

) where

V

is the set of

n

! vertices, each representing a distinct permutation of

n

elements and

E

is the set of symmetric edges such that two permutations (nodes) are connected by an edge iff one can be reached from the other by interchanging its first symbol with any other symbol. The star graph

S

n

is a (

n

 − 1)-regular graph with

n

! nodes and

n

!(

n

 − 1)/2 edges. Recursive hierarchical structure is one of the most attractive and well known properties of star graphs. A dimension

n

star graph can be divided into

n

substars of dimension

n

 − 1 by grouping the nodes with the same symbol at the

i

th position together, 2 ≤ 

i

 ≤ 

n

[see Figure 1].

In this paper, we propose a new recursive hierarchical structure of star graphs. The objective is to redesign shortest routing in star graphs in the light of this new structure and design new efficient algorithms for shortest path multicast algorithms [2] adaptibe to bandwidth and latency requirements.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
A New Hierarchical Structure of Star Graphs and Applications
verfasst von
Wei Shi
Feng Luo
Pradip Srimani
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-28073-3_29