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 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 BangJensen  Algs. for Ham. path and cycle problems in tournamentlike 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  None  Meet 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 
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 nontrivial 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.
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 pProfit Cover is a parameterization of Vertex Cover. We present a fixedparametertractable (fpt) algorithm for pProfit Cover that runs in O(p V + 1.150964^{p}). We combine our algorithm for pProfit Cover with an fptalgorithm for kVertex 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.
We introduce the train tree representation of an interval graph, which is based on the cliqueseparator 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.
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 nontrivial connections between these two areas. In this talk, I will discuss some of these connections focussing on:
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, quasitransitive 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.
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 email your open problems to Gary in advance.
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.
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.
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 largescale optimization problems in gene expression data analysis, clustering, optimal phylogenetic tree algorithms, etc.
The "metaobjective" 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 datamining 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
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 P_{4} nor 2K_{2} as an induced subgraph. We show that the homomorphically full reflexive graphs are precisely threshold graphs, i.e, the graphs that contain none of P_{4}, 2K_{2} and C_{4} as an induced subgraph. We also characterize the reflexive semicomplete digraphs that are homomorphically full.
This is joint work with Jing Huang.
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 NPhard 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) 2dimensional 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.
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.