• Synthesis of Reliable Networks
  • Algorithms for Computing Network Reliability
  • Unranking Spanning Trees
  • Algorithms for the Maximum Clique Problem.
  • Practical Torus Embedding
  • Finding New Cages
  • Graph Reconstruction

    Research Projects

    Synthesis of Reliable Networks

    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).

    TOP of the page. BOTTOM of the page.

    Unranking Spanning Trees

    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

    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.

    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

    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.

    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.

    Dr. Myrvold's Research / maintained by Wendy Myrvold / / revised Nov. 4, 1997