List ranking とは

並列アルゴリズムでは、リストランキングの問題は、リンクされたリスト内の各アイテムの位置またはランクを決定することを含む。つまり、リストの最初の項目には番号1を割り当て、リストの2番目の項目には番号2などを割り当てる必要があります。シーケンシャルコンピュータでこの問題を効率的に解決するのは簡単ですが、並行して解決することはより複雑です。 Anderson&Miller(1990)が書いたように、この問題は並列アルゴリズムコミュニティでは多くのアプリケーションで重要であると考えられていたため、並列アルゴリズムでより一般的に適用できる多くの重要なアイデアが得られました。