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 

May 22  ECS 660  2:30  Andre Raspaud  Injective Colouring of Graphs 
May 25  ECS 660  3:00  Brett Stevens  Covering Arrays, Graph Products and Homomorphisms 
May 25  ECS 660  3:00  Aaron Williams  Universal Cycles for Permutations with Suppressed Symbol 
May 25  ECS 660  3:00  Wendy Myrvold  Investigating Conjectures about Fullerenes 
June 1  _  _  No CAG.  CanaDAM and CS external review 
June 8  ECS 660  2:30  Joergen BangJensen  The Minimum Cost 2edgeconnected Spanning Subgraph Problem: An Evaluation of Neighbourhoods for Local Search 
June 15  EOW 430  2:30  Lior Malka  A Characterization of Vbit Zero Knowledge Protocols 
June 19  ECS 660  2:30  Sean Daugherty  Finding Maximum Independent Sets in Fullerenes 
July 19  EOW 430  10:00  Dan Archambault  FeatureBased Graph Drawing 
For a graph G = (V(G), E(G)), a vertex kcolouring is a mapping from V(G) into {0,1, ... , k1}. We say that a colouring of a graph is injective if its restriction to the neighbourhood of any vertex is injective. The injective chromatic number of a graph G is the least k such that there is an injective kcolouring.
In this talk, we will give a survey of the old and new results concerning the injective colouring. We will also focus on results obtained recently concerning sparse graphs.
Recently graph homomorphisms have been used in the study of optimal software testing protocols, called covering arrays. They optimize testing time when there are internal components known not to interact. Additionally they have prompted a powerful new way to study covering arrays in general, even outside this particular application instance. I will survey their application to this area and show that a previously known construction from design theory is most naturally viewed with graph products and homomorphisms.
De Bruijn constructed circular strings of length 2^{n} where each substring of length n contains a unique binary string. Universal Cycles for permutations of {1,2,...,n} do not directly exist when n >= 3. However, we construct circular strings of length n! where each substring of length n1 is unique. Jackson had proved that such strings exist, and Knuth noticed that every permutation can be inferred by appending the unique ``missing'' final symbol to each substring. If time permits, we will also prove that these Universal Cycles also exist for permutations of a multiset.
Fullerenes are allcarbon molecules whose molecular structures correspond to 3regular planar graphs that have face sizes equal to five or six. Fuigui (Fullerene Interactive Graphical User Interface) is a java program under development whose goal is to aid the exploration of fullerenes and their parameters. This talk will include a selection of interesting open problems about various fullerene parameters. A demonstration of how Fuigui can be used to attack these will be provided.
This is joint work with Bette Bultena, Sean Daugherty, Bradley Debroni, Patrick Fowler, Sameer Girn, Brenna Innes, Marsha Minchenko, and Jennifer Woodcock.
We study the following problem: given a 2edge connected graph with weights on the edges, find a minimum cost spanning subgraph such that the sum of the weights of its edges is as small as possible. We focus on a particular case in which a spanning tree is fixed and the task is augmenting it to a 2edgeconnected graph using only edges from a prescribed set. An application is the extension of an existing communication network to become robust against single linkfailures. The problem is NPhard, even in the particular case above. We compare different construction heuristics and neighborhood structures for local search algorithms. This includes simple neighborhoods such as exchanging a small number of edges, neighborhoods based on shortest paths in the original graph and neighborhoods based on the analogy of this problem with set covering [2]. The analysis, carried out with rigorous statistical methods, indicates that the set covering approach is the best one. On the basis of this result, we implement effective algorithms for solving the set covering formulation, either exactly or heuristically via a reimplementation of the well known algorithm in [1]. The final algorithm outperforms the stateoftheart Memetic algorithm [3] both in speed and solution quality and optimal solutions to the benchmark instances from [3] are found quite consistently.
This is joint work with Marco Chiarandini and Peter Morling.
References:
1. A. Caprara, M. Fischetti, P. Toth, A Heuristic Method for the Set
Covering Problem, Operations Research 47, Vol. 5, (1999) 730743.
2. M. Conforti, A. Galluccio and G. Proietti, EdgeConnectivity
Augmentation and Network Matrices, Lecture Notes in Computer Science,
3353,(2004) 355364.
3. I. Ljubic. Exact and Memetic Algorithms for Two Network Design Problems.
Ph.D. thesis, Faculty of Computer Science, Vienna University of Technology,
November 2004.
Zeroknowledge protocols enable two parties P and V to jointly complete a task such that the privacy of P is not compromised. Hence, they have many applications in cryptography. In this talk we will show that certain zeroknowledge protocols are equivalent to certain functions. These simple functions have two advantages: they can be used for encryption, and they allow us to study zeroknowledge protocols from a combinatorial approach. We will demonstrate the above equivalence using the zeroknowledge protocol for Graph Isomorphism, and then we will show how this example can be generalized to prove the characterization result.
This is joint work with Bruce Kapron and Venkatesh Srinivasan, to appear in ICALP 2007.
A fullerene is a molecule consisting of carbon atoms such that each atom is adjacent to three others, with the bonds forming the edges of pentagonal and hexagonal faces. The resulting fullerene graphs are both planar and cubic. The problem of determining the independence number is NPcomplete for planar cubic graphs, however the complexity for fullerenes was previously unknown. We show that the independence number for fullerenes can be computed in O(n^{6}) time by extending Graver's work on clear fields. The algorithm is outlined and its implementation is compared with that of the previouslybest backtracking algorithm.
The primary problem in graph drawing is producing layouts of undirected graphs in two and three dimensions. We define a graph G=(V,E) as a set of nodes V and a set of relationships or edges E between them. In this research, drawing or layout is defined as an assignment of coordinates to the nodes of the graph in two dimensions.
Most of graph drawing has been focused on producing uniform views of this data. These algorithms treat every node and edge in the data equally. This property can be useful as it produces drawings of uniform node density which satisfy aesthetic criterion proposed by some researchers. However, frequently these drawings can hide lowlevel structure, or local features in the data beyond the immediate adjacency relationships between nodes, and highlevel structure, or how the graph features are interconnected. In fact, many levels may exist in between these extremes in the graph. All three types of structure can remain hidden in drawings of these data sets since these graph drawing algorithms do not explicitly search for it.
In my research, I propose a featurebased approach to graph drawing. In a featurebased approach, I explicitly and sometimes recursively segment out types of structure at various levels in the graph before drawing in order to create drawings which present these types of structure more clearly. My research also explores some interactive exploration techniques for these featurebased hierarchies.
Biography: Daniel Archambault is a Ph.D. student in the Department of Computer Science at UBC. His interests includes graph drawing, information visualization, visualization, and computer graphics.