A 1-approximation of connected graph G = (V. E) is a tree T = (V. E') with the same vertex set such that for every two vertices vertical bar d(G)(u. v) - d(T)(u, v)vertical bar <= 1. A polynomial time algorithm is designed for finding such a tree. (C) 2007 Elsevier B.V. All rights reserved.
展开▼
