Construction of Reliable Series-Parallel Networks: A Combinatorial Approach

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.

Name thesis:degree_name

Master of Science (M.Sc.)

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Saskatchewan

Year dc:date.issued

1983

Author dc:creator

• Neufeld, Eric Michael

Advisor dc:contributor.advisor

• Colbourn, C.J.

Committee member dc:contributor.committeemember

• Cheston, Grant

Handle dc:identifier.uri

https://hdl.handle.net/10388/14729

OAI identifier oai:identifier

oai:harvest.usask.ca:10388/14729