Skip to Main Content (Press Enter)

Logo UNISS
  • ×
  • Home
  • Degrees
  • Courses
  • Jobs
  • People
  • Outputs
  • Organizations
  • Third Mission
  • Expertise & Skills
  • Equipment

Logo UNISS

|

UNIFIND

uniss.it
  • ×
  • Home
  • Degrees
  • Courses
  • Jobs
  • People
  • Outputs
  • Organizations
  • Third Mission
  • Expertise & Skills
  • Equipment
  1. Outputs

Fault-Tolerant Approximate Shortest-Path Trees

Academic Article
Publication Date:
2017
Short description:
Fault-Tolerant Approximate Shortest-Path Trees / Bilò, D., Gualà, L., Leucci, S., Proietti, G.. - In: ALGORITHMICA. - ISSN 0178-4617. - (2017), pp. 1-24. [10.1007/s00453-017-0396-z]
abstract:
The resiliency of a network is its ability to remain effectively functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the broadcasting routing scheme, and we build efficient (i.e., sparse and fast) fault-tolerant approximate shortest-path trees, for both the edge and vertex single-failure case. In particular, for an n-vertex non-negatively weighted graph, and for any constant (Formula presented.), we design two structures of size (Formula presented.) which guarantee (Formula presented.)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size O(n) and stretch factor 3, and for the vertex-failure case of size (Formula presented.) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary spanner can be slightly augmented in order to build efficient fault-tolerant approximate breadth-first-search trees.
Iris type:
1.1 Articolo in rivista
Keywords:
Approximate distances; Fault-tolerant structures; Shortest-path trees; Computer Science (all); Computer Science Applications1707 Computer Vision and Pattern Recognition; Applied Mathematics
List of contributors:
Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido
Handle:
https://iris.uniss.it/handle/11388/202214
Published in:
ALGORITHMICA
Journal
  • Overview

Overview

URL

http://www.springerlink.com/app/home/journal.asp?wasp=b73948a592d54affa300fbefcceb25b0&referrer=parent&backto=linkingpublicationresults,1:100117,1; https://arxiv.org/pdf/1407.0637.pdf
  • Use of cookies

Powered by VIVO | Designed by Cineca | 26.11.1.0