Lad G=(V,E) være en ikke-orienteret graf med n knuder indlejret i et metrisk rum. Betragt følgende problem: tilføj en kant til G, som minimerer den længste omvej i den resulterende graf. Den hurtigste algoritme for dette problem har O(n⁴) køretid og bruger O(n²) plads. Vi forbedrer køretiden til O(n³logn) uden at øge pladsforbruget.
Faktisk finder vores algoritme den længste omvej i G{(u,v)} for alle par af forskellige knuder u og v.
Udgivelsesdato: 23/6-2009