Title: Routing and Timetabling by Topological Search

We discuss how decomposing the search space into homotopy classes can help in finding solutions to combinatorial optimi\-za\-tion problems. Searching any homotopy class then amounts to finding a group function $\psi$ on the arcs of a directed graph such that $\psi$ is cohomologous to a given function $\phi$ and such that $\psi$ has values in a prescribed range. We describe applications to two specific classes of NP-complete problems: routing wires on a chip (where the main tool is solving the cohomology problem in a free group, and a main result the polynomial-time solvability of the wire-routing problem for any fixed number of modules), and finding a periodic timetable (applied to the Dutch railway timetable, where liftings of the period group $C_{60}$ to the integers give the classes to be searched). The methods also imply a characterization of the existence of an isotopy of a compact surface $S$ that brings a given set of disjoint closed curve on $S$ to a given undirected graph embedded on $S$.

1991 Mathematics Subject Classification: 05C85, 05C90, 90B06, 90B10, 90B35

Keywords and Phrases: homotopy, disjoint paths, routing, timetabling, closed curves, compact surface

Full text: dvi.gz 17 k, dvi 39 k, ps.gz 64 k.

Home Page of DOCUMENTA MATHEMATICA