Incremental distance and diameter sequences of a graph: new measures of network performance

Author

Krishnamoorthy, V. ; Thulasiraman, K. ; Swamy, M.N.S.

Author_Institution

Dept. of Electr. & Comput. Eng., Concordia Univ., Montreal, Que., Canada

Volume

39

Issue

2

fYear

1990

fDate

2/1/1990 12:00:00 AM

Firstpage

230

Lastpage

237

Abstract

Two new measures of network performance, namely, the incremental distance sequence and the incremental diameter sequence, are introduced for application in network topology design. These sequences can be defined for both vertex deletions and edge deletions. A complete characterization of the vertex-deleted incremental distance sequence is presented. Proof of this characterization is constructive in nature. A condition for the feasibility of an edge-deleted incremental distance sequence and a procedure for realizing such a sequence are given. Interrelationships between the elements of incremental distance sequences and incremental diameter sequences are studied. Using these results, it is shown that a graph that has a specified diameter and a specified maximum increase in diameters for deletions of vertex sets of given cardinalities can be designed

Keywords

circuit reliability; fault tolerant computing; graph theory; multiprocessor interconnection networks; edge deletions; graph; incremental diameter sequence; incremental distance sequence; measures of network performance; network topology design; vertex deletions; Delay; Distributed computing; Fault tolerance; Graph theory; Multiprocessing systems; Multiprocessor interconnection networks; Process control; Reliability theory; Routing; Topology;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.45208

Filename

45208