𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Complexity of Minimum Ratio Spanning Tree Problems

✍ Scribed by Christopher C. Skiścim; Susan W. Palocsay

Book ID
106414143
Publisher
Springer US
Year
2004
Tongue
English
Weight
349 KB
Volume
30
Category
Article
ISSN
0925-5001

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The expected complexity of Prim's minimu
The expected complexity of Prim's minimum spanning tree algorithm
✍ Chip Martel 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 60 KB

We study the expected performance of Prim's minimum spanning tree (MST) algorithm implemented using ordinary heaps. We show that this implementation runs in linear or almost linear expected time on a wide range of graphs. This helps to explain why Prim's algorithm often beats MST algorithms which ha

The minimum-area spanning tree problem
The minimum-area spanning tree problem
✍ Paz Carmi; Matthew J. Katz; Joseph S.B. Mitchell 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 228 KB