COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2004

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 all-carbon molecules with trivalent polyhedral skeletons, having 12 faces pentagonal and all others hexagonal. Or equivalently, they correspond to 3-regular planar graphs which have twelve 5-faces and the remaining faces are hexagons. Many questions about their chemistry can be cast in graph-theoretical form. This talk deals with three subclasses of the fullerenes:

1. Nut-graphs have exactly one zero eigenvalue in their adjacency spectrum and no zero entries in the corresponding eigenvector;
2. Knot-graphs have exactly one Petrie path; and
3. V-spiral graphs support at least one vertex-spiral that connects all vertices in one contiguous tightly wound Hamiltonian path.

Previous Talks:

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:

1. Is the current CAG slot the best time (Fridays at 2:30) or should be switch back to the 3:30 talks? Or maybe some other time?
2. Would anybody else like to be the CAG organizer? I have been doing it for at least 3 years now, and maybe someone else would like to have a turn?
3. Are there any other types of interesting activities we would like to organize?
4. So far, I have just facilitated visitors that other people invite. Are there any visitors the CAG group or individuals might like to sponsor?
5. Who would like to give a CAG talk in the fall?
6. Is it time to select a different room? If so, where? EOW 430 is convenient for computer science faculty, but less convenient for faculty in math or grad students in computer science.

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 NP-complete 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 edge-decompositions of the lambda-fold complete directed graph lambda-K_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 out-vertices are transmitting, the b in-vertices are listening, and all other n-a-b 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.