COMBINATORIAL ALGORITHMS GROUP

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

Fri. May 1  2:30pm  ECS 660  Valerie King  Averaging samplers to asynchronous computing 
Thurs. May 7  2:30pm  ECS 660  Sean Daughetry  Independent Set Algorithms for Fullerene 
Fri. May 15  2:30pm  ECS 660  Frank Ruskey  Isoperimetric Sequences for Infinite Complete Binary Trees 
Fri. May 15  2:30pm  ECS 660  Bette Bultena  MinimumArea Venn Diagrams 
Tues. May 19  2:30pm  ECS 660  Michelle Edwards  The Diameter of Domination VertexCritical Graphs 
Tues. May 19  2:30pm  ECS 660  Gary MacGillivray  Homomorphisms to local tournaments 
Tues. May 19  2:30pm  ECS 660  Aaron Williams  De Bruijn Cycles for FixedDensity Binary Strings 
Fri. May 22  2:30pm  ECS 660  Peter Dukes  Rational decompositions of highdegree graphs 
Fri. May 22  2:30pm  ECS 660  Jenni Woodcock  Continuing the search for torus obstructions 
Fri. May 22  2:30pm  ECS 660  Sean Daugherty  A LinearTime Algorithm for Finding a Maximum Independent Set of a Fullerene 
Fri. May 29  2:30pm  _  No CAG  CanaDAM 
Fri. June 5  3:00pm  ECS 660  Masoud Ghoreishi  Secret Key Generation in UWB Communication Channels 
Fri. July 3  2:30pm  ECS 660  Leah Howard  Forced Structures in 6nets of Order Ten 
Fri. Aug. 14  11:00am  ECS 660  Sandor Fekete  Approximation algorithms for relay placement 
In the relay placement problem, the input is a set of sensors (given by a set of points in the plane) and a number r>=1, the communication range of a relay. In the onetier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays, such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance one otherwise. The twotier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11approximation algorithm for the onetier version and a PTAS for the twotier version. We also show that the onetier version admits no PTAS, assuming P!=NP.
This is joint work with Alon Efrat, Poornananda Gaddehosur, Joe Mitchell, Valentin Polishchuk, and Jukka Suomela.
Theoretical models of ultrawideband (UWB) radio channels indicate that pairs of UWB radio transceivers measure their common radio channel with a high degree of agreement. In addition, third parties are not able to accurately estimate the state of this common channel. These properties allow generation of secret keys to support secure communications from UWB channel measurements. In this talk, the results of UWB propagation studies are shown that validate the required properties to support secret key generation in a typical indoor environment. Furthermore, key generation algorithms that are employed on the measured data will be introduced. It is shown that key lengths in the order of thousands of bits are obtained which are capable of supporting most popular cryptographic systems. The presentation is also going to report measurements of the spatial and temporal correlation of the UWB channel from which the relative privacy of the secret keys and the rate of secret key generation may be determined.
Byzantine Agreement is a fundamental problem in distributed computing, that is design a protocol to bring processors to agreement on a bit despite a fraction of bad processors behaving to disrupt the outcome. First proposed in 1980, it was proved impossible to solve deterministically in the full information asychronous model which launched some of the early work on randomized algorithms. As the only (randomized) solutions required exponential time, or assumptions of private channels, this spurred the field of cryptography to develop concepts like multiparty secure computation.
Previously, I described a polylog time distributed protocol for the synchronous model to choose a small robust group of processors which can then run Byzantine agreement, leader election, or compile info from processors in a fast, reliable way. The adversary can be assumed to know the messages sent even before it sends its messages in the same round and can be unbounded in computational power. However we do not allow the adversary to dynamically determine which processes to corrupt as the protocol proceeds.
Now through an interesting application of averaging samplers, we extend our results to the much more difficult asynchronous model, bringing the time bounds down from exponential to polylog.
This is joint work with Bruce Kapron, David Kempe, Jared Saia, and Vishal Sanwalani.
Fullerenes are allcarbon molecules with a polyhedral structure in which each carbon atom is bonded with three other carbon atoms and each face of the polyhedron is a hexagon or pentagon. Nanotubes are included in this theoretically infinite group of molecules that were discovered in 1985, and since then fullerenes have received much study.
Finding a maximum independent set of fullerene molecular graphs is of interest from mathematical, computational, and chemical points of view. Such a set can be used to model the bond locations of bulky addends under the assumption that they are too large to bond to adjacent carbon atoms. The problem of determining the maximum independent set order is NPhard for the class of cubic planar graphs and the complexity for the fullerene subclass was previously unknown. This talk sketches a lineartime algorithm for solving the maximum independent set problem for fullerenes.
Analysis showed that the resulting molecule under the vertex independence model is not always stable. A new model, the closedshell independent set, adds some restrictions to the rule of nonadjacency to ensure stability of the resulting molecule after the addition of bulky addends. A backtracking algorithm for finding a maximum closedshell independent set of a fullerene molecule will be presented along with several enhancements that improve the running time.
This is joint work with Wendy Myrvold and Patrick Fowler and extends the work of Jack Graver.
We consider here some isoperimetric problems on the infinite binary tree T, whose leaves are all at the same level. The main quantity of interest is d(n), the minimum number of edges in a cut that has n vertices of T on one side and the rest of T on the other. A simple recurrence relation for d(n) is derived, giving rise to an algorithm that uses O(n) arithmetic operations to evaluate d(n). We also show that d(n) is equal to the least number of parts in any partition of n into parts that are of the form +P or P where P is one less than a power of 2. (This is joint research with Anita Das and Sunil Chandran.)
PolyVenn diagrams are drawn using polyominoes on the integer lattice, where the curves are perimeters and the intersections are smaller polyominoes. Minimumarea Venn diagrams occur when each region in the full diagram is exactly one unit square. We show such diagrams exist in bounding boxes of dimension 2^r X 2^c whenever 0 < c < 2r + 2. We also show that we can expand an existing minimumarea Venn diagram to produce another that fits into a 2^(r+1) X 2^(c+2) bounding box.
A graph G is gammavertexcritical if gamma(Gv) < gamma(G) for every vertex v in V(G)(where gamma(G) denotes the domination number of G). Fulman, Hanson and MacGillivray showed that the diameter, d, of a gammavertexcritical graph G satisfies d <= 2(gamma(G)1) and provided graphs which show that this bound is sharp. We employ their technique to find an upper bound on the diameter of independent domination vertexcritical, total domination vertexcritical, and paired domination vertexcritical graphs. We also present graphs which attain equality in the bounds.
A dichotomy theorem for the complexity of homomorphisms to fixed local tournaments is described. The local tournaments for which the problem is polynomial are those which have the Xunderbar property or are instances of the graft extension. The problem is NPcomplete for all other fixed local tournaments. (This is joint work with Joergen Bang Jensen and Jacobus Swarts.)
De Bruijn cycles are circular binary strings of length 2^{n} that contain every binary string of length n exactly once as a substring. This talk describes the first construction for fixeddensity de Bruijn cycles, which are circular strings of length (n choose k) where each binary string of length n containing k ones is contained exactly once as a shorthand substring.
Let H be a subgraph of G. A rational Hdecomposition of G is a nonnegative rational weighting of the copies of H in G such that every edge of G has total inherited weight equal to 1.
Motivated by applications in design theory and statistics, we discuss the existence problem for rational Hdecompositions of graphs G which have high minimum degree. Estimates on eigenvalues in the Johnson scheme play a central role.
A torus is a surface shaped like a doughnut. 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 is torus embeddable. A minor order obstruction has the additional property that for all edges e, G contract e is also torus embeddable. The longterm goal of our research is to find all the obstructions to the torus, thereby formulating a Kuratowskitype theorem for nontoroidal graphs. In this talk, we will provide an overview of the research to date and discuss recent progress, including exhaustive searches, corrections to previous results, and structural characterizations that will likely guide our focus for finding and proving complete the set of all torus obstructions.
Fullerenes are cubic planar graphs having twelve pentagonal faces and all remaining faces hexagonal. These graphs model fullerene molecules and finding a maximum independent set is of interest from mathematical, computational, and chemical points of view. The problem of determining the maximum independent set order is NPhard for general cubic planar graphs and the complexity for the fullerene subclass was previously unknown. This talk sketches a linear time algorithm for solving the maximum independent set problem for fullerenes.
A (k+2)net of order n is equivalent to k mutually orthogonal Latin squares (MOLS) of order n. This talk will begin with some background on MOLS of order (4m+2). In 1989 Lam, Thiel and Swiercz ruled out the existence of a projective plane of order ten by computer search. I will include a brief discussion of their blockbuilding technique.
The main result is a classification of eleven types of combinatorial structures, some of which must appear in any 6net of order ten. Various block designs and pairwise balanced designs related to the structures will be exhibited. This work is motivated by the quest for a better upper bound on the maximum number of MOLS of order ten.
This talk is based on part of my Ph.D. thesis, supervised by Dr. Peter Dukes.