MIXED SPANNING TREES IN THEORY AND PRACTICE
| Autor: | Jeffrey S. Salowe, Dana Richards |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Discrete mathematics
Theoretical computer science Spanning tree K-ary tree Applied Mathematics Shortest-path tree Minimum spanning tree k-minimum spanning tree Interval tree Theoretical Computer Science Computational Mathematics Computational Theory and Mathematics Kruskal's algorithm Euclidean minimum spanning tree Geometry and Topology Mathematics |
| Zdroj: | International Journal of Computational Geometry & Applications. :277-292 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195999000194 |
| Popis: | A mixed spanning tree is a tree that seeks to combine the properties of a minimim weight spanning tree and shortest path tree. We concentrate on the problem for complete Euclidean graphs. A survey of prior algorithms is given and several new algorithms are proposed. New analyses of some known algorithms are provided. All the algorithms are compared empirically and it is shown that the algorithms with the best known performance bounds, perform the worst in practice. Evidence is given to support the hypothesis that the performance depends on the algorithm's use of long edges. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|