On finding most uniform spanning trees. (English) Zbl 0645.05035
The most uniform spanning tree of a graph with real valued weights assigned to its edges is a spanning tree with the minimal difference between the most and least weighted edges. The paper describes an O(m log n) algorithm for finding such spanning trees (m and n denote the number of edges and vertices respectively.
Reviewer: R.Jiroušek
References:
| [1] | Camerini, P. M.; Maffioli, F.; Martello, S.; Toth, P., Most and least uniform spanning trees, Discrete Appl. Math., 15, 181-197 (1986) · Zbl 0611.05014 |
| [2] | Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, J. Comput. System Sci., 26, 362-391 (1983) · Zbl 0509.68058 |
| [3] | Tarjan, R. E., Data structures and network algorithms, (CBMS-NSF Regional Conferences Series in Applied Math. (1982), SIAM: SIAM Philadelphia, PA) · Zbl 0749.90027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
