|
Organizers |
Computing permutations with stacks and deques
by
Mike Atkinson
University of Otago
Coauthors: M. H. Albert, S. A. Linton
Upper and lower estimates are given for the number of permutations that can be computed using a deque, two stacks in parallel, or two stacks in series
Date received: October 22, 2008
Pathwidth and caterpillar algorithms
by
Michael J. Dinneen
University of Auckland
I will present some old and new results related to the problems of computing pathwidth and finding caterpillars (or their offsprings) in graphs. I will first illustrate a simple linear-time algorithm that determines, for fixed k, whether a graph has pathwidth at most k. I end the talk with some applications and open algorithmic problems in the area. This talk is intended to be self-contained and should be understandable by anyone with a little background in graph theory.
Date received: October 27, 2008
Kernelization lower bounds
by
Rod Downey
Victoria University of Wellington
Kernelization is a method of algorithmic pre-processing which tends to be basis of many practical algorithms, particularly in parameterized complexity. We discuss recent work on demonstrating lower bounds for these problems modulo complexity assumptions as well as applications to density hard instances.
Date received: October 31, 2008
The Maximum Induced Planar Subgraph problem
by
Graham Farr
Monash University
Coauthors: Keith Edwards, Kerri Morgan
The Maximum Induced Planar Subgraph problem asks for the largest set of vertices in a given input graph G that induces a planar subgraph of G. Equivalently, we may ask for the smallest set of vertices in G whose removal leaves behind a planar subgraph. This problem has been linked by Edwards and Farr to the problem of fragmentability of graphs, where we seek the smallest proportion of vertices in a graph whose removal breaks the graph into small (bounded size) pieces. It is also related to the classical Maximum Planar Subgraph problem which is of central importance in graph layout algorithms. This talk describes some algorithms developed for this problem, together with theoretical and experimental results on their performance. Most of the algorithms presented are joint work either with Keith Edwards (Dundee) or Kerri Morgan. The experimental analysis was done by Morgan.
Date received: October 30, 2008
Detecting regular visit patterns
by
Joachim Gudmundsson
NICTA
Coauthors: Anh Pham, Bojan Djordjevic and Thomas Wolle
We are given a trajectory T and an area A. T might intersect A several times, and our aim is to detect whether T visits A with some regularity, e.g. what is the longest time span that a GPS-GSM equipped elephant visited a specific lake on a daily (weekly or yearly) basis, where the elephant has to visit the lake most of the days (weeks or years), but not necessarily on every day (week or year).
During the modelling of such applications, we encountered an elementary problem on bitstrings, that we call LDS (Longest Dense Substring). The bits of the bitstring correspond to a sequence of regular time points, in which a bit is set to 1 iff the trajectory T intersects the area A at the corresponding time point. For the LDS problem, we are given a string s as input and want to output a longest substring of s, such that the ratio of 1s in the substring is at least a certain threshold.
In our model, LDS is a core problem for many applications that aim at detecting regularity of T intersecting A. We propose an optimal algorithm to solve LDS, and also for related problems that are closer to applications, we provide efficient algorithms for detecting regularity.
Date received: October 21, 2008
What is the largest real flow root for a graph?
by
Gordon Royle
University of Western Australia
The flow polynomial of a graph G is the polynomial FG(k) that counts the number of nowhere zero k-flows on G, and the flow roots of G are the real and complex zeros of the flow polynomial. Although the flow polynomial is dual to the chromatic polynomial, much less is known about flow roots than chromatic roots, including the fundamental question of whether there is an absolute upper bound on real flow roots.
For integer flow roots, it is well known that every bridgeless graph has a nowhere-zero 6-flow and it is a difficult unsolved problem whether this extends to nowhere-zero 5-flows. However there is no such upper bound known for real flow roots, although Welsh conjectured that 4 was a possible value for such an upper bound.
In this talk, I will describe a computational attack on this problem that has shown that Welsh's conjecture is not true, and discuss possible replacements for the conjecture.
Date received: November 2, 2008
Algorithmic problems in conservation biology
by
Charles Semple
University of Canterbury
Coauthors: Magnus Bordewich and Andreas Spillner
A central task in conservation biology is measuring, predicting, and preserving biological diversity as species face extinction. Dating back to 1992, phylogenetic diversity is a prominent notion for measuring the biodiversity of a collection of species. This talk gives a flavour of some the combinatorial and algorithmic problems and recent solutions associated with computing this measure.
Date received: November 2, 2008
Symmetry in search
by
Toby Walsh
NICTA and University of New South Wales
Symmetry turns up in many problems. When solving combinatorial problems using search, symmetry may be inherent in the problem (e.g. interchangeable machines to assign to a job) or may arise through modelling it (e.g. naming elements in a set). In either case, symmetry can lead to redundant search, as many symmetrically equivalent blind alleys may be explored wastefully. To avoid this, symmetry-breaking constraints can be added, to exclude all but one of each equivalence class of solutions. Alternatively, the search method can be modified to exclude symmetric parts of the search space. I will describe recent results in this area and outline some of the open problems in the field.
Date received: October 23, 2008