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. 20  EOW 430  1:15  Bruce Shepherd  New Models for Provisioning Flow in Networks 
Jan. 27  EOW 430  2:30  Norbert Zeh  ShortestPath Algorithms for Massive Graphs 
Jan. 28  Cle A 306  2:30  Brad Jackson  Algorithms for the Analysis of Astronomical Data 
Mar. 11  _  _  No CAG.  SE conference on Comb., Graph Theory and Computing 
Mar. 22  DSB C 122  1:00  Sean Daugherty  The Influence and Total Influence Numbers of a Graph 
Mar. 29  EOW 430  2:30  Prasad Tetali  Stochastic Networks, Markov Chains and Phase Transition 
Allocating bandwidth for communicating agents is a problem at the core of dimensioning a network to operate costeffectively. Classical efficient algorithmic techniques such as shortest paths, network flows and linear programming have been the workhorses for solving the network routing models that arise in this context.
In order to be practically solvable, the models themselves drop many of the
reallife side constraints. In this talk, we consider the impact of
incorporating a variety of these constraints on fundamental combinatorial
optimization problems. For the different versions, we also briefly describe
recent telecommunication technologies which impose such constraints on
traffic flow in a network.
Refreshments will be available immediately following the talk in the EOW
Lounge, Room 330.
Shortestpath problems arise in a number of largescale applications such as geographic information systems and web modelling. While shortestpath problems are wellstudied in standard models of computation, they pose serious challenges if the graphs considered are too big to fit into main memory. When dealing with such massive data, it is important to optimize disk accesses rather than computation steps. In particular, locality of access is crucial, which is hard to achieve in graph algorithms in general and in shortestpath computations in particular. This talk gives an overview of the state of the art of algorithms for shortestpath type problems in massive graphs, discussing I/Oefficient and cacheoblivious algorithms for planar graphs and general undirected graphs. At the end of the talk, current challenges are discussed.
Consider a data space partitioned into cells together with a set of data points contained in this space. Our goal is to find the best piecewiseconstant function (constant on the cells) that fits the data. In 1dimensional space we might have a set of points representing the times that photons are emitted from a source of radiation from which we would like to obtain a graph of the intensity of the radiation. In 2dimensional (or 3dimensional) space we might have points representing the positions of galaxies and we would like to graph the density of the galaxies in the various regions of space.
For each partition of the data cells into blocks we have a piecewiseconstant function and we would like to find the partition whose corresponding piecewise function has the highest value. We exhibit an O(N^2) dynamic programming algorithm for finding the optimal partition in a 1dimensional data space. This algorithm can also be used to find the optimal partition of a higher dimensional data space if arbitrary blocks are allowed (not necessarily connected). We exhibit a branch and bound algorithm for finding the optimal partition in a higher dimensional data space if blocks are required to be connected. We don't yet know if this last problem is NPcomplete.
Distance in graphs is a wellstudied area with many practical applications. This talk will introduce two distancebased graph parameters: the influence number and the total influence number. Both of these parameters are new to the literature and are based on applications in psychology that deal with social networks. The influence number uses a set S which maximizes the sum of 1/2^d(u,S) for every vertex u not in S. The total influence number extends this idea to maximize the sum of 1/2^d(u,v) for every vertex u not in S and every vertex v in S. This talk will explore these two parameters, including how to find such a set on various classes of graphs and some complexity results.
The information presented is a result of work by myself, Steve Hedetniemi, Renu Laskar, and Jeremy Lyle from Clemson University, as well as Ulrike Stege and Iris van Rooij from the University of Victoria.
The hardcore lattice gas model is a weighted independent set model which received much attention in the communication networks, theoretical computer science, and statistical physics communities. The standard issue here is in deciding whether the influence of a boundary condition of a large graph is felt at the center of the graph. Connections to mixing rates of Markov chains, information propagation in regular trees and other subtopics make this research area rich and exciting to study. The speaker will attempt to survey various recent developments in this topic, including some of his own contribution. (No prior background in the topic will be assumed.)
Refreshments will be provided immediately following the talk in the EOW 330.