Browsing by Subject "Kruskal’s MST algorithm"

Now showing items 1-1 of 1

    • On Sorting, Heaps, and Minimum Spanning Trees 
      Navarro, Gonzalo; Paredes, Rodrigo (2006)
      Let A be a set of size m. Obtaining the first k ≤ m elements of A in ascending order can be done in optimal O(m + k log k) time. We present Incremental Quicksort (IQS), an algorithm (online on k) which incrementally gives ...