Jump to content

Tree spanner

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 06:39, 21 November 2007 (stub sorting). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

A tree k-spanner (or simply k-spanner) of a graph $G$ is a spanning subtree $T$ of $G$ in which the distance between every pair of vertices is at most $k$ times their distance in $G$ .

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Tree_spanner&oldid=172865392"

Hidden category:

All stub articles