a Department of Informatics, University of Bergen, Norway
b Department of Computer Science and Engineering, University of California, San Diego, USA
c The Institute of Mathematical Sciences, Chennai, India
Abstract:
Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5n+o(n). This is the first algorithm breaking the trivial n!-barrier.