COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2011

1. Due to a famous result by Jack Edmonds, the Maximum Matching problem in graphs is solvable in polynomial time. The Maximum Distance-k Matching problem, however, is known to be NP-complete for all k larger than one (in a distance-k matching, the edges are in pairwise distance at least k). Distance-2 matchings are called induced matchings. We present recent results on maximum distance-k matchings for some specific graph classes.
2. The Dominating Induced Matching problem asks for the existence of an induced matching which intersects all other edges in the graph. It is also known under the name of Efficient Edge Domination problem. The problem is known to be NP-complete. We discuss the case of hole-free graphs and of P₇-free graphs where the problem becomes solvable in polynomial time.

Previous Talks

For our first week, we have a 1.5 hour double feature which includes two talks.

The context of underwater sensor networks (UWSNs) presents special challenges for data transmission. For that context, we examine the merit of using a simple, stochastic transmission strategy based on the ALOHA protocol. The strategy uses a stochastic scheduling approach in which time is slotted, and each network node broadcasts according to some probability during each time slot. We present a closed-form solution to an objective function that guides the assignment of the broadcast probabilities with respect to overall network reliability. We propose an easily distributed heuristic based on local network density and evaluate our approach using numerical simulations. The evaluation results show that even without using explicit control signalling, our simple stochastic scheduling method performs well for data transmission in UWSNs.

A Latin square of order n is a n \times n array of n symbols such that each symbol appears exactly once in each row and exactly once in each column. Two Latin squares of order n are orthogonal if when superimposed, each ordered pair of symbols occurs exactly once. One of the big unsolved problems in design theory is to determine if it is possible to find three or more pairwise orthogonal Latin squares of order 10. This talk describes both theoretical and computational attempts at resolving this question. The talk will conclude with some suggestions for promising areas for continued search.

The research presented in this talk was done in collaboration with Erin Delisle, Mark Ellingham, Leah Howard, Nikolay Korovaiko, Brendan McKay, Alison Meynert, and Ian Wanless.