Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

Victor Chepoi, Feodor Dragan, Ilan Newman +2

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and sim…