The expected complexity of Prim's minimum spanning tree algorithm
From MaRDI portal
Publication:1603503
DOI10.1016/S0020-0190(01)00220-4zbMath1013.68138MaRDI QIDQ1603503
Publication date: 14 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
68P05: Data structures
Cites Work
- 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
- A theorem on the expected complexity of dijkstra's shortest path algorithm
- A randomized linear-time algorithm to find minimum spanning trees
- Fibonacci heaps and their uses in improved network optimization algorithms