A note on distance approximating trees in graphs (Q1582482): Difference between revisions

Let \(G\) be a connected simple graph and let \(\lambda\) denote the largest length of some induced simple cycle in \(G\). It is shown how to construct in linear time, for any choice of a vertex \(u\), a tree \(T\) on the same vertex set such that the distance of any vertex to \(u\) is the same in \(G\) as in \(T\), while distances in both graphs between any two vertices do not differ by more than \(\lfloor \lambda/2 \rfloor + \alpha\), with \(\alpha=1\) for all \(\lambda\), except \(4\) and \(5\) where \(\alpha=2\).