Given n vertices and m edges, which graph would make the best
network topology? We consider this question for
all-terminal reliability, one of the more popular
measures of network reliability.
The best graphs must maximize the number of spanning trees
and have a minimum cut frequency vector.
We have results for almost-complete graphs maximizing
spanning trees (with Gilbert).
With Nadon and von Schellwitz,
we have considered the problem of minimizing the
cut frequency vector for 3-regular graphs.
More detailed information on
reliable network synthesis is available.

TOP of the page. BOTTOM of the page.

We have developed new algorithms for (more information about these algorithms is available):

- Counting small cutsets of a graph (with Kim Cheung).
- Counting k-component forests of a graph. This can be used to compute the numbers of connected spanning n+k edge subgraphs of a planar graph in polynomial time when k is a fixed constant.
- Estimating the numbers of connected spanning n+k edge subgraphs of an arbitrary graph (with Colbourn and Debroni).
- Determining the number of spanning trees each edge of a graph is contained in (with Tsen, Hung, Lin, and Hsu).

TOP of the page. BOTTOM of the page.

An unranking algorithm for a set of k
distinct objects must return each
one of the objects when
given as input each integer from 1 to k.
Selecting an object at random can then be
accomplished by choosing an integer from 1 to k at
random and then unranking.
Work with Colbourn and Neufeld shows
that we can unrank spanning trees in the same
time it takes to count them:
O(n^3) or up to O(n^2.35)
if faster matrix multiplication routines are used.
In fact, we also solve the problem for the
more general case of unranking arborescences
of a directed graph.
The other algorithms for
selecting a random arborescence of a
directed graph
take time proportional to the cover time of the
graph which can be exponential or even infinite.

TOP of the page. BOTTOM of the page.

A * clique *
in a graph is a set of vertices which are
pairwise adjacent.
The CLIQUE problem is to determine
given a graph G and an integer k,
whether G has a k-clique.
Although this problem is NP-complete,
several practical algorithms exist.

With Prsa and Walker, a workbench for analysing
the run times of clique algorithms has been developed.
Faster algorithms for the maximum clique
problem are under investigation.

TOP of the page. BOTTOM of the page.

A graph is embeddable on a surface if it can
be drawn there with no crossing edges.
A torus is shaped like a doughnut
(the kind with a hole in the middle).
With Neufeld, a program for embedding graphs in the
torus (if possible) has been developed.
Although the running time is exponential,
it has proven sufficiently practical to allow
us to compile a large collection of torus obstructions.

TOP of the page. BOTTOM of the page.

The * girth*
of a graph is a size of a smallest cycle.
An (r,g)-cage is an r-regular graph
with girth g having a minimum number of vertices.
With McKay and Nadon, we have verified the (3,9)-cages,
and have determined that (3,11)-cages have order 112.

Gordon Royle has a nice summary of
results for
Cubic Cages.

TOP of the page. BOTTOM of the page.

The vertex reconstruction conjecture asserts that a
graph is uniquely determined (up to isomorphism)
from its collection of vertex-deleted subgraphs.
My Ph. D. work was on this problem.
My M. Math. work was on the edge reconstruction
problem, defined similarly.
Our
insights were enhanced by the extensive use of the computer for computing and
researching the behaviour of small cases.

TOP of the page. BOTTOM of the page.

Home page for Dr. Wendy Myrvold

Publications for Dr. Wendy Myrvold

Department of Computer Science

University of Victoria

Return to TOP of the page.

Dr. Myrvold's Research / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Nov. 4, 1997