k-Level-Buckets

Die Verallgemeinerung von 2-Level-Buckets führt zu k-Level-Buckets. Diese bestehen dann aus k-Arrays der Länge $\mathcal{O}(\sqrt[k]{C})$. Dadurch lassen sich die Speicher- und Zeitkomplexität weiter verbessern, der Implementierungsaufwand steigt jedoch stark an.
Zeitkomplexität:

Literartur:

• Aluja, R.K., K. Mehlhorn, J.B. Orbin, R.E. Tarjan
  Faster Algorithmus for the shortest Path Problem
  J.ACM 37 (1990) p.213-223
  
• Cherkassky, B.V., A.V. Goldberg, T.Ratzig
  Shortest Path Algorithmus: Theory and Experimental Evaluation
  Math. Prog. 73(1996) p.129-174
  
• Cherkassky, B.V., A.V. Goldberg, C. Silverstein:
  Buckets, Heaps, Lists and monoton Priority Queues.
  Proc. 8th Soda, ACM p83-92, 1997 Hot-Queue O$(\sqrt{\log{C}})$