AN O(M-LOG-N) ALGORITHM FOR THE MAX PLUS SUM SPANNING TREE PROBLEM

Authors
PUNNEN AP NAIR KPK
Citation
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
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
89
Issue
2
Year of publication
1996
Pages
423 - 426
Database
ISI
SICI code
0377-2217(1996)89:2<423:AOAFTM>2.0.ZU;2-8
Abstract
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).