Quantum scattering on graphs and a solution to the Traveling Salesman Problem

Robert Schrader Freie Universitaet Berlin, Germany

On any metric graph all Laplace operators may be described in terms of boundary conditions at the vertices. Viewed as a Schroedinger operator each such operator leads to a scattering theory. The resulting on shell S-matrix is always unitary and has both a matrix solution and a representation as a path space sum with contributions involving the total length of the path and the S-matrices associated to the individual vertices traversed. These two representations allow for a new way of solving the Traveling Salesman Problem. In addition for generic lengths of the edges and generic boundary conditions the inverse problem may be solved. The results were obtained in collaboration with V.Kostrykin (Aachen).