COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2006

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 weight-enhanced regular path queries with semantics that allow user-assigned preference (query) weights to be naturally combined with quantitative database link-information 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 weight-enhanced path queries. We present a distributed algorithm for evaluating our proposed queries in a multi-source 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 multi-source 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²), 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 'Programmer-Centric' 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 NP-hard 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 multi-set. The associated algorithm runs in constant amortized time, and the associated ordering also has a simple recursive structure. When specialized to multi-sets containing only 0's and 1's, the result is the previously discovered cool-lex 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.