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 

Jan. 21  Cle B 019  10:00  Sean McGuinness  Perfect Path Double Covers, Matroids, and a Conjecture of Hajos 
Jan. 25  ECS 660  2:30  Jamie Cromack  Assessment Challenges in CS Education 
Mar. 7  ECS 660  2:30  No CAG  SE conference 
Mar. 14  ECS 660  3:00  Naonori Kakimura  SignSolvability of Linear Programming and Linear Complementarity Problems 
Mar. 17  Mac D 105  10:00  Naonori Kakimura  Computing the Inertia from Sign Patterns 
Mar. 20  DSB C112  3:30  Hadi Kharaghani  The energy of matrices and graphs 
Mar. 21  _  _  No CAG  Good Friday 
Mar. 28  ECS 660  2:30  Darian Raad  Multiobjective Evolutionary Algorithms for Discrete Combinatorial Optimization 
Apr. 5  ECS 660  10:00am  Zhu/Srinivasan/Mohar  Coast Combinatorics Conference 
Apr. 9  DSB C108  2:30  Xuding Zhu  Circular choosability of graphs 
Apr. 11  HSD A240  2:30  Xuding Zhu  Colouring games on graphs 
Apr. 18  _  _  No CAG  CS Grad Coffee House 
Apr. 25  ECS 104  2:30  Allan Scott  Parameterized Chess 
It has been suggested that the parameterized complexity class AW[*] is the natural home of kmove games, but to date the number of games known to be complete for this class has remained small. We investigate the complexity of Short Generalized Chess (the problem of deciding whether a chess player can force checkmate in the next k moves) and show that this problem is complete for AW[*].
This is joint work with Ulrike Stege.
A perfect path double cover of a graph G on n vertices is a family P of n paths of G such that each edge of G belongs to exactly two members of P and each vertex of G occurs exactly twice as an end of a path of P. The perfect path double cover conjecture states that that every simple graph has a perfect path double cover. Hajos' conjecture is that for any simple eulerian graph on n vertices, one can partition the edges into at most n/2 cycles.
In this talk, I will discuss how a recent result for matroids leads to some interesting known and unknown theorems/problems for graphs, in particular the perfect path double cover conjecture and Hajos' conjecture.
How do you know whator even if your students are truly learning? Educational assessment means more than just tests; assessment should be an integrated and ongoing process that informs both teaching and learning. This session will offer a vocabulary for building an understanding of the importance of assessment, and introduce an online assessment toolkit being developed at the University of Washington that will focus on CSrelated disciplines. Finally, some simple Classroom Assessment Techniques that work well in CS courses will be presented.
Jamie Cromack is a member of the Education Research Programs group at Microsoft Research. Her focus is the assessment of learning in postsecondary courses in which computational science plays a key role. A specialist in higher education studies, Dr. Cromack taught at the college level for over 15 years and was a new media producer in the educational arena for close to 20 years. Dr. Cromack integrated her technology experience and educational background while working with the National Science Foundation grant, math*ed*ology, and the U.S. Department of Education grant, Preparing Tomorrow's Teachers to Use Technology (PT3).
This talk presents an attempt to connect qualitative matrix theory with linear programming and linear complementarity problems. A linear program max{cx  Ax=b, x >= 0} is said to be signsolvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. Checking the signsolvability of a given linear program turns out to be coNPcomplete. We then introduce a class of signsolvable linear programs in terms of totally signnonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c.
Similarly, we introduce signsolvability for linear complementarity problems(LCPs). We show that a totally signnonsingular matrix characterizes a signsolvable LCP whose coefficient matrix is nonzero diagonal. This characterization leads to an efficient algorithm to obtain the sign pattern of a solution for these LCPs.
The first part of this talk is a joint work with Satoru Iwata.
A symmetric matrix A is said to be signnonsingular if every symmetric matrix with the same sign pattern as A is nonsingular. Hall, Li and Wang (2001) showed that the inertia of a signnonsingular symmetric matrix is determined uniquely by its sign pattern. The purpose of this paper is to present an efficient algorithm for computing the inertia of such symmetric matrices. Our algorithm is based on the matching structure of symmetric bipartite graphs. The running time bound is O(sqrt(n) m log n) for a symmetric matrix of order n with m nonzero entries. In addition, it is shown to be coNPcomplete to decide whether the inertia of a given symmetric matrix is determined by its sign pattern.
This is joint work with Satoru Iwata.
Reference: N. Kakimura and S. Iwata, Computing the Inertia from Sign Patterns. Mathematical Programming, 110, pp. 229244, 2007.
Gutman motivated by applications in chemistry introduced the energy of a graph to be the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of a matrix is defined to be the sum of its singular values. It turns out that only strongly regular graphs attain the maximum possible energy amongst all graphs with a given number of vertices and edges. A similar result holds for (0,1)matrices achieving a maximum possible energy.
No special background is needed for this survey talk.
Genetic algorithms have been evolving since the early 70's, achieving immense success and fame in the process. Multiobjective Evolutionary Algorithms (MOEAs) take this natural paradigm to the next level  an essential jump because few real problems of interest have only a single objective. The last decade has seen a deluge of research in this field, producing such delights as the Nondominated Sorting Genetic Algorithm II (NSGAII). Most MOEAs employ the concept of Paretobased fitness, inspired by the objective of finding an approximation of the Paretooptimal solution set in objective function space. This talk shall present the basic concepts of MOEAs as formulated for discrete combinatorial optimization, including fitness assignment, genetic operations, diversity preservation, elitism, constraint handling and autoadaptation of parameters in a multiobjective environment.
The speakers are: Bojan Mohar, Venkatesh Srinivasan and Xuding Zhu. Everyone is welcome to attend. There is no registration fee. The Coast Combinatorics Conference web page has more details.
Circular colouring of a graph is a variation of the ordinary vertex colouring of graphs, which provides a better model for many periodic scheduling problems. Analogous to the list colouring of graphs, circular choosability of graphs was introduced independently by Mohar and myself. In this talk, I shall survey results in the study of circular colouring of graphs. In particular, I shall explain the application of the combinatorial nullstellensatz to the study of circular choosability of graphs.
A colouring game on planar graphs was invented by Steves in 1981 (published by Scientific America by M. Gardner) as a recreational game. The game remained unnoticed by the graph theoretic community until it was reinvented by Bodlaender in 1991 for general graphs and for the purpose of studying computational complexity. Since then it has attracted much attention. Many interesting problems are studied and interesting results are obtained. In this talk, I shall explain some strategies used in the games that achieve the best known upper bounds for many classes of graphs.
This is a Lansdowne Public Lecture sponsored by the Department of Mathematics and Statistics.