CAG Schedule of Talks: Summer 2002

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Summer 2002

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

Schedule for Friday Talks:

Date Place Time Speaker Abbreviated Title
May 10 EOW 430 3:30 Louis Ibarra A fully dynamic algorithm for recognizing interval graphs using the train tree
May 16 EOW 430 2:00 Jeffrey Shallit Formal Languages and Number Theory
May 17 EOW 430 3:30 Joergen Bang-Jensen Algs. for Ham. path and cycle problems in tournament-like digraphs
May 24 EOW 430 3:30 Problem Session Send Problems to Gary
May 31 EOW 230 3:30 Problem Session continued Send Problems to Gary
June 7 Grad Lounge 3:30 NoneMeet at grad lounge for refreshments
June 14 EOW 430 3:30 Gary MacGillivray The Firefighter Problem
Wed. June 19 HSD A240 3:00 Anna Lubiw Turning Sketched Paths into Shortest Paths
Thurs. June 20 EOW 430 1:30 Pablo Moscato Past and Present Activities
Thurs. July 4 EOW 430 1:30 James Abello Massive Graph Mining
July 12 EOW 430 3:30 Cancelled
July 19 EOW 430 3:30 Gary MacGillivray Homorphically Full Reflexive Graphs and Digraphs
July 26 EOW 230 3:30 John Ellis Searching Solid, convex grids
Aug. 2 EOW 430 3:30 Frank Ruskey Drawing Venn Diagrams
Aug. 23 EOW 230 3:30 Wendy Myrvold Generating Small Latin Squares
Aug. 30 EOW 230 3:30 Ulrike Stege Efficient Implementations Via Combining Tractable Parameterizations

Upcoming Talks:

Generating Small Latin Squares
Wendy Myrvold
Aug. 23, EOW 230, 3:30

A Latin square is an n by n array on n symbols where each symbol appears exactly once in each row and column. Two Latin squares are isotopic if one can be transformed to the other by permuting rows, columns, and/or symbols. Being in the same main class means that in addition, the roles of rows, columns and/or symbols can be interchanged. A third form of equivalence is isomorphism which will be defined in the talk. By using the novel technique of generating only the Latin squares having non-trivial symmetry group, we are able to count the number of isotopy, main, and isomorphism classes up to n = 9 and there is hope the results can be extended to n = 10.

An outstanding open question is whether there exists an orthogonal triple of Latin squares of order 10. The squares of order 10 which have been generated so far have been tested to see if they belong to some orthogonal triple. From these computations, we know that any square in such a triple must have isotopy group order 2^k for some integer k >= 0, as all other squares have been tested. This is joint work with Brendan McKay.

Efficient Implementations via Combining Tractable Parameterizations
Ulrike Stege
Aug. 30, EOW 230, 3:30

We introduce the problem Profit Cover. For a given graph G=(V,E) and an integer p > 0, the goal is to determine PC, a subset of V such that the profit, |E'| - |PC|, is at least p, where E' is the set of edges covered by PC. We show that p-Profit Cover is a parameterization of Vertex Cover. We present a fixed-parameter-tractable (fpt) algorithm for p-Profit Cover that runs in O(p |V| + 1.150964p). We combine our algorithm for p-Profit Cover with an fpt-algorithm for k-Vertex Cover. We show that this results in a more efficient implementation to solve Minimum Vertex Cover than each of the algorithms independently. We also demonstrate the generality of our approach on the example of Planar Dominating Set.

Previous Talks:

A fully dynamic algorithm for recognizing interval graphs using the train tree
Louis Ibarra
May 10, EOW 430, 3:30

We introduce the train tree representation of an interval graph, which is based on the clique-separator graph representation of a chordal graph. The train tree is the basis of the first dynamic algorithm to recognize interval graphs, and it may lead to fast dynamic algorithms for numerous problems on interval graphs, which have applications in areas such as computational biology, archeology, psychology, and scheduling.

Formal Languages and Number Theory
Jeffrey Shallit
Computer Science
University of Waterloo
May 16, EOW 430, 2:00

Number theory is one of the oldest parts of mathematics and the theory of formal languages is one of the oldest parts of theoretical computer science, so it is not surprising there are interesting and non-trivial connections between these two areas. In this talk, I will discuss some of these connections focussing on:

Algorithms for hamiltonian path and cycle problems in tournament-like digraphs
Joergen Bang-Jensen
Department of Computer Science
University of Southern Denmark
May 17, EOW 430, 3:30

We survey results on hamiltonian paths and cycles in digraphs that are structurally related to tournaments. This includes well studied classes of digraphs such as extended semicomplete digraphs, quasi-transitive digraphs and locally semicomplete digraphs (all of which contain tournaments as a subclass) and the class of bipartite tournaments (these do not contain tournaments but are related through the common superclass of multipartite tournaments.

We will discuss the complexity of the hamiltonian path and cycle problems for these classes of digraphs. It turns out that for all the classes above the problems are polynomially solvable but the range of difficulty varies very much from the easiest (almost trivial) case of tournaments to the hardest (very complicated) case of multipartite tournaments.

We will also discuss parallellization of some of the algorithms above for the classes of extended semicomplete digraphs and bipartite tournaments. It turns out that quite a number of tricks are needed in order to obtain (R)NC algorithms for these problems which are closely related to the matching problem in bipartite graphs.

Problem Session
Moderated by Gary MacGillivray
May 24 and also May 31, EOW 430, 3:30

Come one come all and bring your open problems with you. Gary has offered to moderate a problem seesion on May 24 to be continued on May 31 if there is a need for more time. In order to facilitate scheduling, please e-mail your open problems to Gary in advance.

The Firefighter Problem
Gary MacGillivray
June 14, EOW 430, 3:30

Let G be a finite graph and f be a vertex of G. The following one player dynamic game played on G is considered. At time 0 a fire breaks out at vertex f. At each time t > 0, some vertex is defended and then the fire spreads from every vertex on fire to every undefended neighbour of such a vertex. Once a vertex is on fire it remains on fire for the duration of the game, and similarly for defended vertices. The game ends when the fire can no longer spread. The object of the game is to minimize the number of vertices on fire when the it ends. Perhaps unsurprisingly, the corresponding decision problem is NP complete even when restricted to bipartite graphs. Strategies and complexity results will for various classes of graphs willbe discussed.

Turning Sketched Paths into Shortest Paths
Anna Lubiw
June 19, 3:00-4:00 pm, Room HSD A240

Given n point obstacles in the plane and some "sketches'' of disjoint paths that wind amongst the points, we give an efficient algorithm to turn the sketched paths into shortest paths that still wind amongst the points in the same way -- i.e. that are homotopic to the original paths. This problem of computing shortest homotopic paths has application to graph drawing, wire routing in circuit board design, and motion planning. The talk will include background on geometric shortest path problems.
This is joint work with Alon Efrat and Stephen Kobourov.

An Overview of My Past and Present Activities and Possible
Collaborations and Synergies with Researchers at University of Victoria
Dr. Pablo Moscato
Department of Computing and Automation and
Department of Systems Engineering FEEC - UNICAMP
Thursday, June 20, 1:30 - 2:30, EOW 430

The objective of this talk is to present a brief account of my current and past activities in research, particularly in the field of metaheuristics and memetic algorithms, as well as in other fields of computational complexity. Our most recent project was recently awarded with a Brazilean federal grant to study problems related with micro array data analysis, a revolutionary new tool that is changing the way in which scientific inference of genetic networks must be conducted. At the group of Software Engineering for Complex Systems, we are currently working in a variety of topics in Bioinformatics involving large-scale optimization problems in gene expression data analysis, clustering, optimal phylogenetic tree algorithms, etc.

The "meta-objective" of the talk is that it may serve as a starting point for a Collaboration with professors and graduate students at University of Victoria, particularly in problems related to data-mining and pattern recognition and the computational complexity of feature selection problems. The talk will also offer a very personal view and account of facts, and a proposal for a quest of a systematic approach to bridge the gap between theory and practice, with Bio informatics as a leading uniting force.

The material for this talk is based on past and current work with M.G. Norman (Dept. of CS, University of Edinburgh), L. Buriol (AT&T Research Labs), Prof. Carlos Cotta (University of Málaga, Spain), R. Berretta (USF, Brazil), F. Xhafa and M.J. Blesa (UPC, Barcelona), F. Von Zuben and L. Gomes (UNICAMP, Brazil).

Memetic Algorithms' Home Page - http://www.densis.fee.unicamp.br/~moscato/memetic_home.html
TSPBIB Home Page - http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html
The Hamiltonian Page - http://www.densis.fee.unicamp.br/~moscato/Hamilton.html
Fractal Instances of the TSP - http://www.densis.fee.unicamp.br/~moscato/FRACTAL_TSP_home.html

Homorphically Full Reflexive Graphs and Digraphs
Gary MacGillivray
July 19, EOW 430, 3:30

A graph (digraph) is homomorphically full if it contains every homomorphic image as a subgraph (subdigraph). The homomorphically full irreflexive graphs are known to be precisely the graphs that contain neither P4 nor 2K2 as an induced subgraph. We show that the homomorphically full reflexive graphs are precisely threshold graphs, i.e, the graphs that contain none of P4, 2K2 and C4 as an induced subgraph. We also characterize the reflexive semicomplete digraphs that are homomorphically full.

This is joint work with Jing Huang.

Searching solid, convex grids
John Ellis
July 26, EOW 230, 3:30

Suppose we are searching a building for an omniscient and fast moving intruder. We can capture the intruder if we place a guard at both ends of a corridor containing the intruder, but if we leave any avenue open the intruder will for sure slip past the guards.

What is the minimum number of guards and using what strategy can ensure the capture of the intruder?

This problem is nicely modelled by the "node search number" of a graph. In this model, the edges represent corridors and the nodes represent the confluence of corridors.

It happens that this problem is not only entertaining but significant, because this parameter is identical to other important graph parameters, among them: vertex separation, pathwidth and interval thickness. Computing the value of the the parameter is in general an NP-hard problem, but it can be computed in polynomial time on some restricted graph families, such as trees and some perfect graphs.

Here we consider the family of "solid (no internal holes) convex (no indentations in the periphery) 2-dimensional grid graphs". It turns out that computing the search number on these graphs in polynomial time is possible by a method that is intuitively simple, but the proof of optimality is not obvious.

This research is joint work with Hongbing Fan.

Drawing Venn Diagrams
Frank Ruskey
Aug. 2, EOW 430, 3:30

Preamble: I will be giving one of the two invited talks at the 10th Annual Conference on Graph Drawing on August 26 (http://www.cs.uci.edu/~gd2002/). This is a practice for that talk. It is also my first experience at preparing and giving a powerpoint presentation. The talk is not very technical and has lots of pretty pictures.

Abstract:

Venn diagrams have long been used as an aid in understanding set containment relationships and certain logical arguments. They also have interesting combinatorial properties. In this talk we survey some of what is known about Venn diagrams, with particular emphasis on the aesthetic and extremal properties of the drawings. Connections with graph drawing, of which there are many, will be emphasized.


CAG Schedule of Talks: Summer 2002 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised August 22, 2002