CAG Schedule of Talks: Summer 2007

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Summer 2007

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).

Schedule for Talks:

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 Bang-Jensen The Minimum Cost 2-edge-connected Spanning Subgraph Problem: An Evaluation of Neighbourhoods for Local Search
June 15 EOW 430 2:30 Lior Malka A Characterization of V-bit 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 Feature-Based Graph Drawing

Previous Talks:

Injective Colouring of Graphs
Andre Raspaud
LaBRI, Université Bordeaux I
Tuesday May 22, 2:30pm, ECS 660

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

On Friday May 25, we will have 3 practice talks, the first two are from
CanaDAM in Banff and the third is from the CMS-MITACS Joint Meeting in Winnipeg.

Covering Arrays, Graph Products and Homomorphisms
Brett Stevens
School of Mathematics and Statistics
Carleton University
Currently visiting at UVic
Friday May 25, 3:00pm, ECS 660

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.

Universal Cycles for Permutations with Suppressed Symbol
Aaron Williams
Friday May 25, 3:00pm, ECS 660

De Bruijn constructed circular strings of length 2n 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.

Investigating Conjectures about Fullerenes
Wendy Myrvold
Friday May 25, 3:00pm, ECS 660

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.

The Minimum Cost 2-edge-connected Spanning Subgraph Problem:
An Evaluation of Neighbourhoods for Local Search
Jorgen Bang-Jensen
Department of Mathematics and Computer Science
University of Southern Denmark
Friday June 8, 2:30pm, ECS 660

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.

A Characterization of V-bit Zero Knowledge Protocols
Lior Malka.
Friday June 15, 2:30pm, EOW 430

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.

Finding Maximum Independent Sets in Fullerenes
Sean Daugherty
Tuesday June 19, 2:30pm, ECS 660

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(n6) 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.

Feature-Based Graph Drawing
Dan Archambault
Dept. of Computer Science, UBC
Visiting Dr. Melanie Tory
Thursday July 19, 10:00am, EOW 430

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.


CAG Schedule of Talks: Summer 2007 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised Sept. 11, 2007