Multi-source spanning trees: algorithms for minimizing source eccentricities

✍ Scribed by H.Brendan McMahan; Andrzej Proskurowski

• Book ID: 104294204
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 212 KB
• Volume: 137
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00262-2

✦ Synopsis

We present two e cient algorithms constructing a spanning tree with minimum eccentricity of a source, for a given graph with weighted edges and a set of source vertices. The ÿrst algorithm is both simpler to implement and faster of the two. The second approach involves enumerating single-source shortest-path spanning trees for all points on a graph, a technique that may be useful in solving other problems.