CAG Schedule of Talks: Spring 2002

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Spring 2002

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).

Schedule for Friday Talks:

Date Place Time Speaker Abbreviated Title
Jan. 11 EOW 430 3:30 Minko Markov Vertex Separation of MOPS
Jan. 18 EOW 430 3:30 John Boyer Simplified O(n) Planarity Testing and Related Problems
Jan. 21 Cle C 112 3:30 Gary MacGillivray Some Proofs that there are Infinitely Many Primes
Jan. 25 EOW 430 3:30 Mark Weston Generating Symmetric Venn Diagrams
Feb. 1 EOW 430 3:30 John Chambers Hunting for Torus Obstructions
Feb. 11 Cle C 112 3:30 Cobus Swarts Fermat's Two Squares Theorem
Feb. 22 EOW 430 3:30 Scott Effler Cayley Graphs: 2-Generated and Cubic
Mar. 1 EOW 430 3:30 Kelly Choo Gray codes for k-colourings of a graph
Mar. 8 EOW 430 3:30 No CAG? SE Conference, Boca Raton
Mar. 15 EOW 430 3:30 Narsingh Deo Computing the 3-D Molecular Structure in Parallel
Mar. 29 No talk- Good Friday.
Apr. 5 EOW 430 3:30 Frank Ruskey Counting Aperiodic Strings
Apr. 12 EOW 430 3:30 Hamish Carr A Heuristic for 4-Colouring a Planar Graph
Apr. 19 EOW 430 3:30 Jonathan Jedwab Designing the IEEE 802.12 Transmission Code
Apr. 26 EOW 430 3:30 Joergen Bang-Jensen Finding Minimum Cost Cycles in Digraphs

Upcoming Talks:

Designing the IEEE 802.12 Transmission Code
Jonathan Jedwab
April 19, EOW 430, 3:30

In 1995 the Institute of Electrical and Electronic Engineers (IEEE) approved the 802.12 international standard for transmitting information at 100Mbit/s over copper telephone cabling. Under this standard, messages are encoded from 5-bit data groups into 6-bit code groups prior to transmission. The code mapping was chosen to satisfy physical, economic and social constraints simultaneously.

Nine years after designing this code as a Hewlett-Packard employee and presenting its properties to the IEEE I have permission to explain its underlying structure. I shall show how the code was found using a combination of geometrical insight, combinatorial reasoning and computer search.

Finding Minimum Cost Cycles in Tournament-like Digraphs with Real-valued Costs on the Vertices
Joergen Bang-Jensen
Department of Computer Science
University of Southern Denmark
April 26, EOW 430, 3:30

Let D be a digraph with real-valued costs on the vertices and let the cost of a cycle be the sum of the costs of its vertices. Clearly, if we allow negative costs then it is NP-hard to find a minimum cost cycle since the hamiltonian cycle problem can be posed in this way.

In this talk we show how to solve the problem of finding a minimum cost cycle in polynomial time for some classes of digraphs that are structurally related to tournaments. This includes well studied classes of digraphs such as extended semicomplete digraphs and quasi-transitive digraphs. As it will be clear from the talk the solution for quasi-transitive digraphs builds heavily on their nice decomposition properties and strong relation to extended semicomplete digraphs.

This is joint work with Gregory Gutin and Anders Yeo of Royal Holloway, University of London.

Previous Talks:

A practical polynomial time algorithm for the vertex separation of Maximal Outerplanar Graphs (MOPS)
Minko Markov
Jan. 11, EOW 430, 3:30

VERTEX SEPARATION is an important, NP-complete graph problem. It is eqivalent to several other problems, the most well-known among which is PATHWIDTH. It is known that vertex separation is solvable in polynomial time on graphs of bounded treewidth. However, even the best known algorithm on bounded-treewidth graphs can hardly be called practical. Therefore, there are efforts to design practical algorithms for that graph parameter on even more restricted graph classes.

We present an outline of an exact vertex separation algorithm on maximal outerplanar graphs, which are a subset of graphs of treewidth two. The work is still in progress, right at this moment. The presentation will introduce the results achieved so far, and will make a comparison with the algorithms for the vertex separation of ordinary trees.

Simplified O(n) Planarity Testing and Related Problems
John Boyer
Jan. 18, EOW 430, 3:30

A graph is planar if it can be drawn on the plane with vertices at unique locations and no edge intersections except at the vertex endpoints. Due to the wealth of interest from the computer science community, there are a number of remarkable but complex O(n) planarity algorithms. The presentation will discuss a new simplified O(n) planarity testing algorithm that is based on embedding one edge of an input graph at a time while maintaining planarity of the embedded portion of the graph.

This new algorithm is interesting not only for the ease with which it can be implemented and proven both correct and O(n) but also because it forms the foundation for simplified solutions to numerous related problems, including planar embedding, the identification of a Kuratowski subgraph (a portion of a non-planar input graph which obstructs planarity), outerplanar graph embedding and obstruction identification, and the search for subgraphs homeomorphic to K2,3 and K3,3.

Some Proofs that there are Infinitely Many Primes
Gary MacGillivray
Monday, January 21, 2002, 3:30 PM, Clearihue C-112

Paul Erdos talked about "The Book", kept by God, in which the perfect proofs of mathematical theorems are recorded. He also said that you need not believe in God but, as a mathematician, you should believe in The Book.

The volume "Proofs from THE BOOK", by Martin Aigner and Gunter Zeigler is dedicated to Erdos' memory. The first section of *this* book is entitled "Six proofs of the infinity of primes". I don't have the courage to assert that I can do all six proofs in 50 minutes (we shall see), hence the title.

Generating Symmetric Venn Diagrams
Mark Weston
Jan. 25, EOW 430, 3:30

A Venn diagram is a collection of simple closed curves in the plane with the property that all possible intersections of the interiors and exteriors of these curves are nonempty and connected. A Venn diagram with n curves is referred to as a an n-Venn diagram. We consider n-Venn diagrams with n-fold rotational symmetry and examine the dual graph of these diagrams. A number of interesting combinatorial properties leads to a simple generation scheme and we survey and expand on some work on generating symmetric 7- and 11-Venn diagrams.

Hunting for Torus Obstructions
John Chambers
Feb. 1, EOW 430, 3:30

A torus is a surface shaped like a doughnut. A graph is toroidal if it embeds on the torus with no crossing edges. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus.

The aim of our research is to find all the obstructions to the torus (both minor order and topological). To date, we have found 239,322 topological obstructions and 16,629 minor order obstructions. Previously, only a few thousand had been determined. This talk discusses the techniques used to find these obstructions.

Fermat's Two Squares Theorem
Cobus Swarts
Feb. 11, Cle C 112, 3:30

In this talk we will look at Fermat's two squares theorem which states the condition under which an integer may be written as the sum of two squares. This was judged by Hardy as one of the most beautiful results in number theory. Although this theorem is old, we present a fairly recent proof of one of the key lemmas. If time permits we will briefly mention some other results in this direction.

Cayley Graphs: 2-Generated and Cubic
Scott Effler
Feb. 22, EOW 430, 3:30

Let the generating set X be a subset of a group G. The directed Cayley graph is the graph whose vertex set is G and where arcs leaving vertex g in G are of the form g --> gx for each x in X. Undirected Cayley graphs can be defined similarly.

This talk will explore previously known as well as new results about Cayley graphs with respect to enumeration, isomorphism and Hamiltonicity.

Gray codes for proper k-colourings of a graph
Kelly Choo
March 1, EOW 430, 3:30

A graph has a Gray code for proper k-colourings if is possible to list all its proper k-colourings in such a way that consecutive elements in the list differ in the colour of exactly one vertex. In this talk, I will show the existence of Gray codes for proper k-colourings for several graphs and values of k.

Computing the 3-D Molecular Structure in Parallel
Narsingh Deo
Center for Parallel Computation
School of Computer Science
University of Central Florida
March 15, EOW 430, 3:30

Determining the three-dimensional structure of a bio macromolecule (e.g., a protein) is an extremely important and computationally challenging problem. One approach involves using NMR (nuclear magnetic resonance) spectroscopy, by which a small subset of the n(n-1)/2 inter-atomic distances in an n-atom molecule are measured. Furthermore, these distance measurements are not exact, but each lies within an upper and a lower bound. Computing the coordinates of the n points (atoms) in the 3-D Euclidean space which conforms to the NMR distance measurements is referred to as the molecular conformation problem.

We use an edge-weighted, complete graph of order n, embedded in the 3-D space to model the n-atom molecule. First, the triangle inequality is applied to tighten the distance bounds, in parallel. The bounds are further tightened by applying the tetrangle inequality (resulting from the Cayley-Menger determinants) to all quadruples of atoms, also in parallel. Parallel algorithms are essential to keep execution times within reasonable limits. Only edge-disjoint sets of 4-node subgraphs can be processed concurrently. Finding such edge-disjoint subgraphs is equivalent to constructing a large set of 2-(n, 4, 1) packing designs. A number of other interesting problems involving design theory as well as graph theory arise in this context. [Background Reference: R. Kumar and N. Deo, "Computational Experience with a Parallel Algorithm for Tetrangle Inequality Bound Smoothing," Bulletin of Mathematical Biology (1999), Vol. 61, pp. 987-1008]

Counting aperiodic strings with given elementary function evaluations
Frank Ruskey
Apr. 5, EOW 430, 3:30

For fixed k and values t[1..k] we try to count the number of aperiodic strings a[1..n] for which Sk(a) = tk, where Sk is the k-th elementary symmetric function. The alphabet of the string a is a ring R. After setting up a general framework, specific results are given for the following cases:

Using (b), we are able to count the number of odd degree monic irreducible polynomials over F(q) whose next 3 leading coefficients are prespecified and whose degree is odd. The efficacy of our formulae will be stated in rops, the number of ring operations necessary to evaluate them. Part of the development involves a new multivariate form of Mobius inversion.

A Heuristic for 4-Colouring a Planar Graph
Hamish Carr
Computer Science, University of British Columbia
Apr. 12, EOW 430, 3:30

We describe a heuristic for 4-colouring a planar graph based on Kempe's method of recolouring Kempe chains. The heuristic gives rise to a special family of graphs which cause the algorithm to cycle. The structure of these graphs is described, and a modified heuristic is presented. In practice the method is found to always succeed in 4-colouring a graph in O(n^2) time. A proof that it works would be another proof of the 4-colour problem.

I shall also describe how this heuristic relates to the successful proofs of the 4-colour problem, and the obstacles that remain to developing this heuristic into a proof. This is joint work with Bill Kocay (Computer Science, University of Manitoba).


CAG Schedule of Talks: Spring 2002 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised April 17, 2002