|
|||||
|
|
A distance approximating trees |
|
| Authors: | Vojtech Blint |
| Institution: | aDepartment of Mathematics, Faculty of Operation and Economics of Transport and Communications, University of Žilina, Slovakia |
| Abstract: | 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 |dG(u,v)−dT(u,v)| 1. A polynomial time algorithm is designed for finding such a tree. |
| Keywords: | Distance approximating trees Tree spanner |
| 本文献已被 ScienceDirect 等数据库收录！ | |