# Research

• 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

## Algorithms for Computing Network Reliability

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.

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

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