Multi-source spanning trees: algorithms for minimizing source eccentricities
| Autor: | H. Brendan McMahan, Andrzej Proskurowski |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Graph center
021103 operations research Spanning tree Applied Mathematics 0211 other engineering and technologies Network 0102 computer and information sciences 02 engineering and technology Minimum spanning tree Shortest-paths spanning trees 01 natural sciences Connected dominating set Communications Graph Distributed minimum spanning tree Algorithm 010201 computation theory & mathematics Kruskal's algorithm Multicast Euclidean minimum spanning tree Reverse-delete algorithm Discrete Mathematics and Combinatorics Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics. 137(2):213-222 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/s0166-218x(03)00262-2 |
| Popis: | We present two efficient 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 first 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect