Buckets, Heaps, Lists, and Monotone Priority Queues (1997)
Boris Cherkassky, Krasikova St, Andrew V. Goldberg
We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox and a heap. We use the new data structure to obtain an O(m +...
Buckets, Heaps, Lists, and Monotone Priority Queues (1997)
Boris Cherkassky, Krasikova St, Andrew V. Goldberg
We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox and a heap. Our data structure improves operation bounds. We...
Heap-on-Top Priority Queues (1996)
Boris V. Cherkassky, Krasikova St, Andrew V. Goldberg
We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox [9] and a heap. We use the new data structure to obtain an...
Negative-Cycle Detection Algorithms (1996)
Boris V. Cherkassky, Krasikova St, Andrew V. Goldberg
We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy. We study various...