| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420764 | Discrete Applied Mathematics | 2008 | 13 Pages |
Abstract
A 1-approximation of connected graph G=(V,E)G=(V,E) is a tree T=(V,E′)T=(V,E′) with the same vertex set such that for every two vertices |dG(u,v)−dT(u,v)|⩽1|dG(u,v)−dT(u,v)|⩽1. A polynomial time algorithm is designed for finding such a tree.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vojtech Bálint,