The expected complexity of Prim's minimum spanning tree algorithm

DOI10.1016/S0020-0190(01)00220-4zbMath1013.68138MaRDI QIDQ1603503

Charles U. Martel

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

data structuresgraph algorithmsminimum spanning treeexpected performance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

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

This page was built for publication: The expected complexity of Prim's minimum spanning tree algorithm