Raziskovalni matematični seminar - Arhiv

We report on work in progress on the question of finding good paths for bicycles in a traffic network with (possibly coordinated) traffic lights. While the standard dynamic shortest path problem in time-dependent networks with cyclic time windows is known to be easy, we study the related problem of finding routes that keep a small number of stops.  We show that the problem is strongly NP-hard for paths and trails, whereas it is weakly NP-hard for walks. We give a pseudo-polynomial algorithm for this third option. Further, we report about ongoing work on designing algorithms for the case of variable speeds and the employment of appropriate power consumption and recovery models for bicycles for the above formulated problem.

Joint work with Markus Rogge, Robert Scheffler & Martin Strehler.

In this talk I will describe some progress in analytic number theory, from the pioneering work by Dirichlet and Riemann to the Selberg class of L-functions. This talk will be informative and should be accessible to non-specialists.

Let Γ denote a Q-polynomial distance-regular graph with diameter D and valency k ≥ 3. By the result of H. Lewis, the girth of Γ  is at most 6. In this talk, we give a classification of graphs that attain this upper bound. We show that Γ  has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D +1, or to a generalized hexagon of order (1, k -1).