Improving Bounds on Link Failure Tolerance of the Star Graph

Authors

David Walker, University of Nevada, Las VegasFollow
Shahram Latifi, University of Nevada, Las VegasFollow

Document Type

Article

Publication Date

7-2010

Publication Title

Information Science

Volume

180

Issue

13

First page number:

2571

Last page number:

2575

Abstract

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)⩽(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.

Keywords

Computer networks--Reliability; Distributed parameter systems; Multiprocessors--Reliability; Parallel processing (Electronic computers); Reliability--Mathematical models

Disciplines

Digital Communications and Networking | Electrical and Computer Engineering | OS and Networks | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

Repository Citation

Walker, D., Latifi, S. (2010). Improving Bounds on Link Failure Tolerance of the Star Graph. Information Science, 180(13), 2571-2575.