Automatic Tuning of the SkewedKruskal Algorithm

Mattia Lecchi () and Giovanni Righini ()
Additional contact information
Mattia Lecchi: University of Milan, Department of Computer Science
Giovanni Righini: University of Milan, Department of Computer Science

A chapter in Theory, Algorithms, and Experiments in Applied Optimization, 2025, pp 171-198 from Springer

Abstract: Abstract The SkewedKruskal algorithm is an implementation of Kruskal algorithm where the edge list is recursively sorted on demand, mimicking the well-known QuickSort algorithm. We investigate the issue of improving the time performance of SkewedKruskal by guessing the position of the largest edge of a minimum cost spanning tree (MST), in order to avoid sorting unnecessary edges. For this purpose, a statistical analysis is performed on the distribution of the edge weights in some classes of randomly generated weighted graphs, so that the position of the largest MST edge can be guessed by sampling a relatively small number of edge weights. Experimental results are reported to evaluate the effectiveness of the techniques proposed.

Keywords: Minimum cost spanning tree; Kruskal algorithm; QuickSort (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-91357-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9783031913570

DOI: 10.1007/978-3-031-91357-0_9

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().