Cyclic routing algorithms on graphs with applications to robotics and logistics

Eugene Levner (Holon Institute of Technology, Israel)

Abstract: There are many various cyclic scheduling problems on graphs, the

most popular among them being the TSP. We consider another, less popular,

problem whose history starts with the cyclic PERT/CPM and loop scheduling

in parallel computing. Its relationship with other graph problems will be

discussed. A survey of old and new combinatorial algorithms starting with

Romanovskii (1967) and Dantzig-Blattner-Rao (1967) will be presented.

Open questions related to algorithm complexity will be also discussed.

(A joint work with Vladimir Kats).