COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
CAG will resume in January. Have a great holiday!
Date  Place  Time  Speaker  Abbreviated Title 

Sept. 15  ECS 660  2:30  Alex Thomo  Enhanced Regular Path Queries on Semistructured Databases 
Sept. 29  No CAG.  2:30  _  Open house preparation. 
Oct. 6  ECS 660  2:30  Marina Barsky  A New Algorithm for Fast AllAgainstAll Substring Matching 
Oct. 13  DSB C 128  2:30  LillAnne Jackson  Toward a Programmer Centric Itanium Multiprocessor Memory Consistency Model 
Oct. 27  ECS 660  2:30  Frederic Dorn  Dynamic Programming and Fast Matrix Multiplication 
Nov. 3  ECS 660  2:30  Aaron Williams  Multiset Permutations are also Cool 
Nov. 10  Elliott 062  2:30  Sean Daugherty  Algorithms for Maximum Independent Sets of Fullerenes 
Regular path queries are the basic navigational component of virtually all the mechanisms for querying semistructured data commonly found in information integration applications, Web and communication networks, biological data management etc. We start by proposing weightenhanced regular path queries with semantics that allow userassigned preference (query) weights to be naturally combined with quantitative database linkinformation for driving the navigation. Motivated by the fact that the main applications of semistructured data involve distributed data sources, we focus next on the distributed evaluation of the weightenhanced path queries. We present a distributed algorithm for evaluating our proposed queries in a multisource setting. Our algorithm is general in the sense that it does not assume a known topology of the network and it can work using asynchronous communication. This algorithm can also be used to solve multisource shortest path problems for which the full graph is not known in advance.
We present a new and efficient algorithm to solve the "threshold all vs. all" problem, which involves searching of two strings (with length N and M respectively) for finding all maximal approximate matches of length at least S and with up to K differences. The algorithm is based on a novel graph model, and it solves the problem in time O(NMK^{2}), which is a significant improvement over the previously known time bound for this problem.
In the past decade every new processor was faster and had more features than its predecessor. This was made possible by successively smaller transistors with fast switching times. However, the power consumption of these devices has forced the architectural industry to stop these upward curves. Instead, the available floorspace on today's chips contains two copies of the same processor (dual cores). Industry experts speculate that the number of cores on a chip will double every year for the forseeable future. These same experts express concern about the number of programmers able to write correct and efficient programs for such systems. Writing such programs requires familiarity with the memory ordering rules (or the memory consistency model) for each specific architecture.
The talk begins with a survey of work on defined shared memory multiprocessor consistency models and outlines the difficulties of writing correct and efficient code for such systems. This is followed by a proposal for a 'ProgrammerCentric' memory consistency model for Intel's Itanium processor.
This is joint work with Lisa Higham and Jalal Kawash.
We give a novel approach for solving NPhard optimization problems that combines dynamic programming and fast matrix multiplication. The technique is based on reducing much of the computation involved to matrix multiplication. Our approach is applied to obtain the fastest algorithms for various graph problems such as the fastest algorithm for Planar Independent Set, Planar Dominating Set, and Planar Hamiltonian Cycle. The exponent of the running time is depending heavily on the running time of the fastest matrix multiplication algorithm that is currently O(n^{2.376}).
We present a simple iterative rule for generating every permutation of a multiset. The associated algorithm runs in constant amortized time, and the associated ordering also has a simple recursive structure. When specialized to multisets containing only 0's and 1's, the result is the previously discovered coollex ordering for combinations.
This talk will present the state of the art of algorithms for finding the independence number of fullerene graphs. Currently, the fastest algorithms require exponential time.