CAG Schedule of Talks: Summer 2011

COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2011

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca). To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at http://mailman.csc.uvic.ca/mailman/listinfo/cag

Schedule for Talks:

Date Place Time Speaker Abbreviated Title
Fri. May 6 ECS 660 2:30pm Dimitri Marinakis Stochastic Scheduling for Underwater Sensor Networks
Fri. May 6 ECS 660 3:00pm Wendy Myrvold Searching for three MOLS of order 10
Fri. May 28 _ _ No CAG. CanaDAM Conference, May 31-June 3
Fri. June 24 _ _ No CAG. IWOCA Conference, June 20-June 22
Tues. Aug. 23 SSM A102 3:30pm Andreas Brandst├Ądt On Variants of Matchings

On Variants of Matchings
Andreas Brandst├Ądt, University of Rostock
Tuesday, August 23, 3:30pm-4:30pm, SSM A102

  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 P7-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.

Stochastic Scheduling for Underwater Sensor Networks
Dimitri Marinakis

Friday May 6, 2:30pm-3:00pm, ECS 660

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.

Searching for a maximum set of mutually orthogonal latin squares of order 10
Wendy Myrvold

Friday May 6, 3:00pm-4:00pm, ECS 660

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.


CAG Schedule of Talks: Summer 2011 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Aug. 16, 2011