AN IN-DEPTH EMPIRICAL-INVESTIGATION OF NONGREEDY APPROACHES FOR THE MINIMUM SPANNING TREE PROBLEM

被引:5
作者
GLOVER, F
KLINGMAN, D
KRISHNAN, R
PADMAN, R
机构
[1] UNIV TEXAS,GRAD SCH BUSINESS & COMP SCI,COLL NAT SCI,AUSTIN,TX 78712
[2] CARNEGIE MELLON UNIV,SCH URBAN & PUBL AFFAIRS,DECIS SYST RES INST,PITTSBURGH,PA 15213
关键词
NETWORKS; MINIMUM SPANNING TREE; NON-GREEDY APPROACHES; REORGANIZATION;
D O I
10.1016/0377-2217(92)90317-3
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper details the design, implementation, and testing of a one edge pass non-greedy algorithm for the minimum spanning tree problem. The use of network labeling procedures, and path weights to screen entering edges, provides a novel implementation of this algorithm. The choice of data structures also allows for an efficient implementation of reoptimization procedures, which have hitherto never been studied. Comprehensive results on the performance of both the greedy and non-greedy algorithms in optimization and reoptimization modes under various screening criteria, graph topologies, sizes and densities, and weight distributions are presented. The empirical results based on 855 problems bear out Tarjan's conjecture that greedy algorithms have a competitive advantage over non-greedy algorithms for the minimum spanning tree problem, except in special cases. However, for the problems tested, when a small percentage of edge weights are changed, non-greedy approaches are competitive with greedy algorithms in reoptimization mode.
引用
收藏
页码:343 / 356
页数:14
相关论文
共 35 条
[1]  
Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st
[2]  
BARR R, 1979, INFOR, V17, P16
[3]  
Berge C., 1965, PROGRAMMING GAMES TR
[4]  
Boruvka O., 1926, PRACE MORAVSKE PRIRO, V3, P37
[5]  
Brennan J. J., 1982, Operations Research Letters, V1, P113, DOI 10.1016/0167-6377(82)90010-4
[6]  
Cheriton D., 1976, SIAM Journal on Computing, V5, P724, DOI 10.1137/0205051
[7]  
Choquet G., 1938, CR HEBD ACAD SCI, V206, P310
[8]  
Dijkstra E. W., 1959, NUMER MATH, P269, DOI DOI 10.1007/BF01386390
[9]  
Edmonds J., 1971, MATH PROGRAM, V1, P127, DOI [10.1007/BF01584082, DOI 10.1007/BF01584082]
[10]  
GABOW HN, 1985, CUCS21482 U COL TECH