This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (n, k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K-PASTED-TREE, that allows the construction of a LHG for every pair (n. k) such that n >= 2k. Secondly we present another graph constraint for LHG, namely K-DIAMOND, which is equivalent to K-PASTED-TREE in terms of capability to construct LHGs for any pair (n. k). The interest of K-DIAMOND lies in the fact that, for a given k, K-DIAMOND allows us to construct more regular graphs than K-PASTED-TREE does. A k-regular graph shows the minimal number of links required byak-connected graph, leading to minimal flooding cost. The paper formally shows. in particular, that there are an infinite number of pairs (n, k), such that there exists a k-regular LHG for the pair (n. k) that satisfies K-DIAMOND and does not satisfy K-PASTED-TREE. (C) 2009 Elsevier B.V. All rights reserved.

Investigating the existence and the regularity of Logarithmic Harary Graphs / Baldoni, Roberto; Bonomi, Silvia; Querzoni, Leonardo; TUCCI PIERGIOVANNI, Sara. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 410:21-23(2009), pp. 2110-2121. [10.1016/j.tcs.2009.01.041]

Investigating the existence and the regularity of Logarithmic Harary Graphs

BALDONI, Roberto;BONOMI, Silvia;QUERZONI, Leonardo;TUCCI PIERGIOVANNI, sara
2009

Abstract

This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes n. Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (n, k) (where k is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely K-PASTED-TREE, that allows the construction of a LHG for every pair (n. k) such that n >= 2k. Secondly we present another graph constraint for LHG, namely K-DIAMOND, which is equivalent to K-PASTED-TREE in terms of capability to construct LHGs for any pair (n. k). The interest of K-DIAMOND lies in the fact that, for a given k, K-DIAMOND allows us to construct more regular graphs than K-PASTED-TREE does. A k-regular graph shows the minimal number of links required byak-connected graph, leading to minimal flooding cost. The paper formally shows. in particular, that there are an infinite number of pairs (n, k), such that there exists a k-regular LHG for the pair (n. k) that satisfies K-DIAMOND and does not satisfy K-PASTED-TREE. (C) 2009 Elsevier B.V. All rights reserved.
2009
flooding overlay networks; graph constraints; logarithmic harary graphs
01 Pubblicazione su rivista::01a Articolo in rivista
Investigating the existence and the regularity of Logarithmic Harary Graphs / Baldoni, Roberto; Bonomi, Silvia; Querzoni, Leonardo; TUCCI PIERGIOVANNI, Sara. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 410:21-23(2009), pp. 2110-2121. [10.1016/j.tcs.2009.01.041]
File allegati a questo prodotto
File Dimensione Formato  
VE_2009_11573-230664.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.17 MB
Formato Adobe PDF
1.17 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/230664
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact