Parallel algorithms are also described for a weighted version of the problem of selecting an element of given rank from an unsorted array and for the selection of the kth smallest element in a matrix with sorted columns.
The k shortest paths algorithm is applied to obtain a parallel implementation of a dynamic programming algorithm for the list Viterbi decoding problem, where one must find the most probable state sequences of a Markov process, given noisy observations of the state transitions. Algorithms are developed for the problem of computing quickest paths for the transmission of data through a graph, where the time to send data across an edge depends on the capacity of the edge and on its latency.