Minimum-weight spanning tree algorithms. A survey and empirical study
From MaRDI portal
Publication:5953166
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
performance evaluationgraph algorithmsminimum spanning treelinear-time algorithmsnetwork optimisation
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