Invited Speakers

Generic placeholder image

Maria Chudnovsky

Princeton University, USA
Induced subgraphs and tree decompositions

Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction: the talk will be a survey of these results.

Generic placeholder image

Anna Lubiw

University of Waterloo, Canada
Token Swapping

Given a graph where every vertex has exactly one labeled token, a swap exchanges the tokens at the two endpoints of an edge. The situation can be modelled as an exponentially large Cayley graph with a vertex for each permutation of the labels and an edge for each swap. It is easy to see that the Cayley graph is connected (every permutation of labels can be realized by a sequence of swaps). Of interest are the diameter of the Cayley graph (the worst case length of a sequence of swaps) and the complexity of computing the minimum length sequence of swaps to realize a given permutation. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robotmotion planning, game theory, and engineering. I will survey this work and talk about hardness and approximation algorithms for token swapping on trees.

Generic placeholder image

David Peleg

Weizmann Institute of Science, Israel
New directions in network realization

Network realization problems concern situations where given a specification S, detailing the desired values of a certain network parameter, it is required to construct a network adhering to S, or decide that no such network exists. A variety of network realization problems have been studied over the past 70 years, focusing mainly on the parameters of vertex degrees and inter-vertex distances. The talk will present some recent developments in the area of network realization.

Generic placeholder image

Alfred Wassermann

University of Bayreuth, Germany
Search for combinatorial objects using lattice algorithms - revisited

In 1986, Kreher and Radziszowski first used the famous LLL algorithm to construct combinatorial designs. Subsequently, lattice algorithms have been applied to construct a large variety of objects in design theory, coding theory and finite geometry. Unfortunately, the use of lattice algorithms in combinatorial search is still not well established. Recently, a new enumeration strategy based on "limited discrepancy search" was used to further improve the power of this method. In this talk, we will describe the search strategy based on lattice basis reduction, compare it to widely used backtracking algorithms and integer linear programming algorithms, and will outline the recent progress.