Repository logo
 

Construction of Reliable Series-Parallel Networks: A Combinatorial Approach

Date

1983

Journal Title

Journal ISSN

Volume Title

Publisher

ORCID

Type

Degree Level

Masters

Abstract

The study of network reliability is motivated practically by the appearance of more and more large- and medium-scale networks, and by every indication that the computer network will soon be a primary means of communication for most people. For sparse networks, the probability that the network is connected drops rapidly as the probability of failure of sites or lines increases. This is perhaps counter to intuition since even a sparse network on a small number of vertices ( < 15 ) may have millions or billions of connected spanning subnetworks (i.e., every site may communicate with every other site). There are no "perfect" components: any element of a network may fail and thus study of the construction of the most reliable networks becomes quite important. Reliability may mean many things; current definitions can be roughly grouped into two classes, the deterministic and the probabilistic. We are interested in the latter and identify reliability with probabilistic connectedness. Even so, many different definitions of probabilistic connectedness are used. Of the common probabilistic network models, we choose one where lines fail independently with equal probability and sites do not fail. The exact measure of reliability is simple if we can efficiently count connected spanning subgraphs classified by number of links. This thesis studies maximal series-parallel graphs (equivalent to a class of graphs known as 2-trees) and closely related graphs. We coin the term generalized fan to describe those maximal series-parallel networks with the fewest vertices of degree two. We find a simple recurrence to count connected spanning subgraphs of generalized fans and a formula which computes reliability of generalized fans without any information about subgraph counts. We show that those maximal series-parallel graphs with the fewest vertices of degree two have more connected spanning subgraphs and are more reliable than any other maximal series-parallel graph. We show the rank polynomial of all generalized fans are identical, suggesting that generalized fans have a similar internal structure. We also give subgraph counts and reliability of the n-vertex wheel. In certain applications it is necessary to know the probability that a subnetwork has no bridges, for example, to avoid routing problems. We prove that generalized fan networks are most likely to have bridgeless subgraphs.

Description

Keywords

Citation

Degree

Master of Science (M.Sc.)

Department

Computer Science

Program

Computer Science

Part Of

item.page.relation.ispartofseries

DOI

item.page.identifier.pmid

item.page.identifier.pmcid