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 

Sept. 24  Grad center  3:30  None  Meet for beer at grad center 
Oct. 29  Cle C 112  2:30  Aaron Williams  Perfect Elimination Orders of Chordal Graphs 
Nov. 5  EOW 430  2:30  Peter Dukes  Complete Bipartite Directed Graph Decompositions and EnergyLimited Sensor NetworkS 
Nov. 12  EOW 430  2:30  Reading break  
Nov. 19  EOW 430  2:30  No CAG  Combinatorial Potlatch in Vancouver Nov. 20 
Nov. 26  DSB C 113  2:30  Sudhakar Ganti  Applying Network Tomography for Network Overlays 
Dec. 6  EOW 430  2:30  Patrick Fowler  Three aspects of fullerenes  nuts, knots and spirals 
This talk presents the concepts of Network Tomography and the principles of traffic matrix estimation. This will be further applied to the Network Overlay designs using flexible service models. The talk will highlight some of the recent work in this area and what further research needs to be done.
Fullerenes are allcarbon molecules with trivalent polyhedral skeletons, having 12 faces pentagonal and all others hexagonal. Or equivalently, they correspond to 3regular planar graphs which have twelve 5faces and the remaining faces are hexagons. Many questions about their chemistry can be cast in graphtheoretical form. This talk deals with three subclasses of the fullerenes:
Please join us at the grad center at 3:30pm for beer or your favorite refreshments.
Here are some questions to consider before the meeting:
A graph is chordal if it does not contain an induced cycle of length four or greater. Chordal graphs are characterized by the existence of vertex orderings called perfect elimination orders. These orders are the basis for solving many NPcomplete problems (including vertex colouring and maximum independent set) in linear time. For this reason, algorithms that quickly generate perfect elimination orders are of considerable practical value. One such algorithm is called maximum cardinality search. In this talk, we will prove the correctness of this simple and elegant algorithm. The proof is "new" in the sense that it differs from the original proof, and I have not seen it before.
In this talk, we examine edgedecompositions of the lambdafold complete directed graph lambdaK_{n} into complete bipartite directed subgraphs K_{a,b} as a model for communication in sensor networks. The n vertices of lambda K_{n} correspond to nodes in the network. A constituent K_{a,b} in the edge decomposition corresponds to a scheduled time slot for communication in which the a outvertices are transmitting, the b invertices are listening, and all other nab vertices are asleep (powered down). The decomposition guarantees lambda time slots for a transmission from any node x to any other node y. However, it is also desirable to minimize interference by a third node x'. We outline various constructions for these graph decompositions, with particular emphasis on properties minimizing interference.
This is joint work with Charles Colbourn and Violet Syrotiuk.