Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloThe impact of dynamic events on the number of errors in networks
Anno di pubblicazione2016
Formato
  • Elettronico
  • Cartaceo
Autore/iGlacet C.; Hanusse N.; Ilcinkas D.
Affiliazioni autoriCNR, IEIIT, Turin, Italy; CNRS and Univ. Bordeaux, LaBRI, UMR 5800, Talence, F-33400, France
Autori CNR e affiliazioni
  • CHRISTIAN GLACET
Lingua/e
  • inglese
AbstractIn order to achieve routing in a graph, nodes need to store routing information. In the case of shortest path routing, for a given destination, every node has to store an advice that is an outgoing link toward a neighbor. If this neighbor does not belong to a shortest path then the advice is considered as an error and the node giving this advice will be qualified a liar. This article focuses on the impact of graph dynamics on the advice set for a given destination. More precisely we show that, for a weighted graph G of diameter D with n nodes and m edges, the expected number of errors after M edge deletions is bounded by O(n(dot operator)M(dot operator)D/m). We also show that this bound is tight when M=O(n). Moreover, for M' node deletions, the expected number of errors is O(M'(dot operator)D). Finally we show that after a single edge addition the expected number of liars can be ?(n) for some families of graphs.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da1
Pagine a12
Pagine totali-
RivistaTheoretical computer science
Attiva dal 1975
Editore: Elsevier - Lausanne ;
Paese di pubblicazione: Paesi Bassi
Lingua: inglese
ISSN: 0304-3975
Titolo chiave: Theoretical computer science
Titolo abbreviato: Theor. comp. sci.
Numero volume della rivista627
Fascicolo della rivista-
DOI10.1016/j.tcs.2016.02.012
Verificato da referee-
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-84959169302)
Parole chiaveDistance changes, Dynamics, Errors, Graph, Network, Routing information
Link (URL, URI)http://www.scopus.com/inward/record.url?eid=2-s2.0-84959169302&partnerID=q2rCbXpz
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
  • ICT.P07.006.001 : Reti wireless per il monitoraggio ambientale e info-mobilità
Progetti Europei-
Allegati