Contents
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.
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.
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.
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.
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.
Go to TOP.
Analysis- Progress and Proposed Research
One tactic for designing a reliable
network is to construct possible network topologies
and then to compare their reliabilities.
One objective of this research is to provide
fast, and effective tools for network
analysis to facilitate this process.
Many of the problems studied involve
significant open problems in the area
of graph algorithms.
Go to TOP.
Cutsets
The reliability of a network is a function of
the numbers of cutsets that a graph has
of each size.
Colbourn and Ramanathan
devised the first polynomial time algorithm for
counting the cutsets of size at most lambda + k
where lambda is the minimum cutsize and k
is a constant.
A new algorithm
with faster asymptotic complexity
than that of Colbourn and Ramanathan
has been developed with the aid of
my graduate student, Kim Cheung.
This research suggests that generalizing the algorithm
of Ball and Provan
for counting minimum cutsets
is a promising avenue for further improvement.
Go to TOP.
Spanning Trees and Trees with a few Extra Edges
The reliability of a network
can also be expressed as a function of
the number
of connected spanning subgraphs
that a graph has of each size.
Liu and Chow
designed a polynomial time algorithm
for counting the number of spanning
subgraphs of a planar
graph consisting of a tree plus
at most some constant number of edges.
We have simplified the proofs in their
paper and have also suggested ways of
speeding up their algorithm.
The next step is
to consider graphs
that are close to being planar.
Go to TOP.
Synthesis- Progress and Proposed Research
In general, when comparing the
reliability of two networks, it is essential to
know the component operation probability.
However, for particular numbers of communication
centers and links, there are networks which
are most reliable regardless of the
operation probability of the links.
A network is
uniformly-most reliable
if the probability that it
is operational is at least as good as
the probability that any other graph with
the same
order and size is operational,
regardless
of the probability of component failure.
Obviously, uniformly-most reliable networks
would be of particular interest to a network designer.
Go to TOP.
Cutsets
A necessary condition for uniform optimality is that the edge connectivity
is maximized. In addition, the number of minimum cuts
must be minimized.
Certain circulants have been proposed as
a network topology because they are nice in this regard.
However, we have shown
(with Nadon and von Schellwitz)
that within a large subclass of 3-regular
graphs satisfying these conditions, circulants are in fact
the worst graphs you could select.
This work classifies the almost minimum cuts
(those of size equal to the minimum plus one)
in quasi-prisms (a subclass of 3-regular graphs
which includes cycle permutation graphs and generalized
Petersen graphs).
Our next step is to generalize these results
to encompass all 3-regular graphs,
or to consider special classes of 4-regular graphs.
Ultimately, the goal is to obtain results
that are applicable to all graphs.
Go to TOP.
Spanning Trees
It is easy to show that a uniformly-most
reliable network must maximize the number of spanning
trees.
Futhermore,
the question of which graphs on n
vertices and m edges have the maximum number
of spanning trees is interesting in its own right.
We examine the family of graphs whose complements are a union of paths
and cycles
(with Gilbert)
and develop a very simple algebraic technique for comparing
the number of spanning trees. With our algebra, we obtain a simple
proof of a result of Kel'mans- that evening out path lengths increases
the number of spanning trees in the complement graph. We provide a
similiar characterization for cycles. The theorems we develop enable
us to characterize the graphs in this family with a maximum number of
spanning trees. This result was also obtained earlier by Petingi
in his Ph. D. thesis (a paper is in preparation
with C. Suffel and F. Boesch)
and they also show (except for a few cases) that
the best graphs are almost regular.
We are working together to finish off this proof.
Go to TOP.
General Results
Boesch
conjectured that uniformly-most
reliable networks always exist.
We found an infinite family of counterexamples
to this conjecture in 1991
but later realized that this result had been proved
(even before Boesch made his conjecture) by Kel'mans in 1981.
Next, we showed
(with Colbourn and Harms)
that reliability polynomials
can ``cross twice''.
Or in other words, that
it is possible to find two graphs G and H
so that
that G is more reliable
both for small and large component operation
probabilities, yet H is more reliable in the
intermediate ranges.