Home page for Dr. Wendy Myrvold

Publications for Dr. Wendy Myrvold

Department of Computer Science

University of Victoria

**
Contents
**

- The Network Model
- Analysis- Progress and Proposed Research
- Synthesis- Progress and Proposed Research

The *all-terminal reliability* of a network
is the
probability that
all the communication centers can communicate with
each other.
Under this model,
a network is operational if the associated graph
is connected.
Since the probability of component failure
is generally not known, it is typically reasonable
to assume that components operate with equal
probability *p*.
This research is focussed exclusively on the all-terminal reliability problem.
Colbourn's monograph
provides an excellent survey of reliability results
up to 1987.

Go to TOP.

Go to TOP.

Go to TOP.

For graphs that are not planar,
no polynomial time algorithm is known
for counting the connected spanning subgraphs
which consist of a spanning tree plus a small number
of additional edges.
An open problem is whether this
counting question is #P-complete.
For these graphs, we have proposed
a Monte Carlo algorithm for
estimating the
number of connected spanning subgraphs
which are a tree plus a small number of additional edges.
An offshoot of this work was the
development
(with Colbourn and Neufeld)
of a fast algorithm for generating a
random spanning tree of a graph.
This algorithm also permits solution of the more general
problem of unranking a spanning
arborescence of a directed graph.

Go to TOP.

Our second objective is to completely
characterize uniformly-most reliable
networks when they exist.
A first step is to establish various
traits of these networks to narrow
down the search space.
The ultimate goal is to be able to provide
an efficient construction which
given the number of communication
centers and links would
output the uniformly-most reliable
network if it exists, or the
best network for
the estimated component operation
probability if it does not exist.

Go to TOP.

Go to TOP.

The next step is to consider the families of almost complete graphs where the vertices in the complement are of degree two or degree three. We first plan to examine small cases with the aid of the computer before formulating conjectures regarding the optimal graphs.

There is also potential for future research in the
case that the graphs considered are fairly sparse.
The graphs with the most spanning trees are
known for up to
*n+3* edges (*n* is the number of vertices).
Our approach to extending these results
is to study how to subdivide a 3-regular
graph some fixed number of times
in order to maximize the number of spanning trees.

It seems apparent that a graph maximizing
the number of spanning trees
must have vertex degrees as regular
as possible.
This ``obvious'' condition seems very difficult
to prove for the general case
even though all known optimal examples have this
property.
A long term goal is to develop tools
for showing that almost regularity is a requirement.
This may be approached either as an optimization
question (considering the eigenvalues of the
Kirchoff matrix) or
by producing spanning tree increasing
operations which enable us to convert
any graph which is not almost regular
in its degrees to an almost regular
one with more trees.

Go to TOP.

It is possible for nonisomorphic graphs to have
the same reliability polynomials,
that is, they are *reliability-equivalent*.
We have characterized theta-graphs
(a *theta-graph* is composed of a cycle
and a path which connects two vertices on the cycle)
which
are reliability equivalent.

Some general questions that we intend to investigate further are the relationships between various graph parameters such as girth and diameter to the reliability. The work with Nadon indicates that girth is an important parameter for 3-regular graphs when considering the small cutsets. Spurred by this research, we developed a backtrack program to find 3-regular cages (a cage is a graph of minimum order with a given girth). Brendan McKay has enhanced our code and added some isomorphism screening. We have been able to discover some new cages with the resulting program (these still need to be verified but we suspect they are correct).

**Revision date: July 8, 1996.**