COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2007

For a graph G = (V(G), E(G)), a vertex k-colouring is a mapping from V(G) into {0,1, ... , k-1}. 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 k-colouring.

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.

CAG: Conference Talk Practice Day
Friday May 25, 3pm-4pm

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ⁿ 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 n-1 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 multi-set.

Fullerenes are all-carbon molecules whose molecular structures correspond to 3-regular 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 2-edge 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 2-edge-connected graph using only edges from a prescribed set. An application is the extension of an existing communication network to become robust against single link-failures. The problem is NP-hard, 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 re-implementation of the well known algorithm in [1]. The final algorithm outperforms the state-of-the-art 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) 730-743.
2. M. Conforti, A. Galluccio and G. Proietti, Edge-Connectivity Augmentation and Network Matrices, Lecture Notes in Computer Science, 3353,(2004) 355-364.
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.

Zero-knowledge 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 zero-knowledge protocols are equivalent to certain functions. These simple functions have two advantages: they can be used for encryption, and they allow us to study zero-knowledge protocols from a combinatorial approach. We will demonstrate the above equivalence using the zero-knowledge 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 NP-complete 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⁶) time by extending Graver's work on clear fields. The algorithm is outlined and its implementation is compared with that of the previously-best 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 low-level structure, or local features in the data beyond the immediate adjacency relationships between nodes, and high-level 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 feature-based approach to graph drawing. In a feature-based 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 feature-based 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.