Minimum-weight spanning tree algorithms. A survey and empirical study

DOI10.1016/S0305-0548(00)00007-1zbMath1018.90062OpenAlexW1966658892MaRDI QIDQ5953166

Khalil S. Hindi, Cüneyt F. Bazlamaçci

Publication date: 9 April 2002

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0305-0548(00)00007-1

zbMATH Keywords

performance evaluationgraph algorithmsminimum spanning treelinear-time algorithmsnetwork optimisation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

Remarks on the application of genetic algorithm and tabu search method to nonlinear spanning tree problems, Computing all efficient solutions of the biobjective minimum spanning tree problem, A new approach for the multiobjective minimum spanning tree, Enhanced second order algorithm applied to the capacitated minimum spanning tree problem, A voltage drop limited decentralized electric power distribution network, Unnamed Item, On symbolic OBDD-based algorithms for the minimum spanning tree problem, Unnamed Item, Ectropy of diversity measures for populations in Euclidean space, Universal scaling behaviour in weighted trade networks, Dynamic programming for spanning tree problems: application to the multi-objective case, Empirical study of exact algorithms for the multi-objective spanning tree

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Priority queues with update and finding minimum spanning trees
• Dioïds and semirings: Links to fuzzy sets and other applications
• Computational Methods for Minimum Spanning Tree Algorithms
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
• Finding Minimum Spanning Trees
• A randomized linear-time algorithm to find minimum spanning trees
• On the History of the Minimum Spanning Tree Problem
• A simpler minimum spanning tree verification algorithm
• Fibonacci heaps and their uses in improved network optimization algorithms