COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
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: 2Generated and Cubic 
Mar. 1  EOW 430  3:30  Kelly Choo  Gray codes for kcolourings 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 3D 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 4Colouring 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 BangJensen  Finding Minimum Cost Cycles in Digraphs 
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 5bit data groups into 6bit 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 HewlettPackard 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.
Let D be a digraph with realvalued 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 NPhard 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 quasitransitive digraphs. As it will be clear from the talk the solution for quasitransitive 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.
VERTEX SEPARATION is an important, NPcomplete graph problem. It is eqivalent to several other problems, the most wellknown 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 boundedtreewidth 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.
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 nonplanar input graph which obstructs planarity), outerplanar graph embedding and obstruction identification, and the search for subgraphs homeomorphic to K_{2,3} and K_{3,3}.
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.
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 nVenn diagram. We consider nVenn diagrams with nfold 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 11Venn diagrams.
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, Ge 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.
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.
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.
A graph has a Gray code for proper kcolourings if is possible to list all its proper kcolourings 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 kcolourings for several graphs and values of k.
Determining the threedimensional 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(n1)/2 interatomic distances in an natom 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 3D Euclidean space which conforms to the NMR distance measurements is referred to as the molecular conformation problem.
We use an edgeweighted, complete graph of order n, embedded in the 3D space to model the natom 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 CayleyMenger determinants) to all quadruples of atoms, also in parallel. Parallel algorithms are essential to keep execution times within reasonable limits. Only edgedisjoint sets of 4node subgraphs can be processed concurrently. Finding such edgedisjoint 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. 9871008]
For fixed k and values t[1..k] we try to count the number of aperiodic strings a[1..n] for which S_{k}(a) = t_{k}, where S_{k} is the kth 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:
We describe a heuristic for 4colouring 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 4colouring a graph in O(n^2) time. A proof that it works would be another proof of the 4colour problem.
I shall also describe how this heuristic relates to the successful proofs of the 4colour 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).