Ap. Punnen et Kpk. Nair, AN O(M-LOG-N) ALGORITHM FOR THE MAX PLUS SUM SPANNING TREE PROBLEM, European journal of operational research, 89(2), 1996, pp. 423-426
Citations number
8
Categorie Soggetti
Management,"Operatione Research & Management Science
In a graph in which each edge has two weights, the max + sum spanning
tree problem seeks a spanning tree that has the minimum value for the
combined total of the maximum of one of the edge weights and the sum o
f the other weights among all the spanning trees in the graph. Exploit
ing an efficient data structure, an O(m log n) algorithm is presented
for solving this problem. This improves the currently known bound of O
(mn).