Efficient fault-tolerant routings in networks
type: Item
instance of: scholarly article
title: Efficient fault-tolerant routings in networks
zbMATH Open document ID: 0622.94034
DOI: 10.1016/0890-5401(87)90063-0
author: Danny Dolev
author: Michael Fischer
author: Andrei Broder
author: Barbara B. Simons
published in: Information and Computation
publication date: 1987-01-01T00:00:00Z
review text: We analyze the problem of constructing a network with a given number of nodes which has a fixed routing and which is highly fault tolerant. A construction is presented which forms a ''product route graph'' from two or more constituent ''route graphs.'' The analysis involves the surviving route graph, which consists of all nonfaulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a ''padding theorem'' which allows one to add nodes to a graph and to extend a previous routing.
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4010406
zbMATH Keywords: product route graph
zbMATH Keywords: surviving route graph
MaRDI profile type: Publication
full work available at URL: 0890-5401(87)90063-0
OpenAlex ID: W2095205044
cites work: Graphs as models of communication network vulnerability: Connectivity and persistence
cites work: A new look at fault-tolerant network routing
cites work: On a measure of communication network vulnerability
cites work: Graph multiplication
cites work: Q5685178
cites work: Q4769104
description: scientific article; zbMATH DE number 4010406