Research Projects

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.

Algorithms for Computing Network Reliability

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

1. Counting small cutsets of a graph (with Kim Cheung).
2. 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.
3. Estimating the numbers of connected spanning n+k edge subgraphs of an arbitrary graph (with Colbourn and Debroni).
4. Determining the number of spanning trees each edge of a graph is contained in (with Tsen, Hung, Lin, and Hsu).

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.

Algorithms for the Maximum Clique Problem

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.

Practical Torus Embedding

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.

Finding New Cages

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

TOP of the page. BOTTOM of the page.

Graph Reconstruction

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.