Premium
Networks immune to isolated line failures
Author(s) -
Farley Arthur M.,
Proskurowski Andrzej
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120404
Subject(s) - line (geometry) , routing (electronic design automation) , set (abstract data type) , computer science , class (philosophy) , tree (set theory) , tree network , combinatorics , computer network , mathematics , artificial intelligence , geometry , programming language
A network is immune to a set of failures if all message transfers between operative sites can be completed in the presence of such failures. A set of line failures is isolated if no two failing lines are incident to the same site. Several classes of isolated line failure immune (ILFI) networks are defined, including a class with fewest lines for a given number of sites. An algorithm is presented which turns an arbitrary tree into one of these minimum ILFI networks and computes routing tables for the new network.