List ranking
http://dbpedia.org/resource/List_ranking
In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
rdf:langString
List Ranking bezeichnet die Aufgabe, den Elementen einer verketteten Liste ihren Rang innerhalb der Liste zuzuordnen. Der Rang eines Listenelements ist dabei definiert als der Abstand zum letzten Listenelement. Dieser Artikel beschränkt sich auf einfach verkettete Listen, außerdem soll das letzte Element einer Liste dadurch gekennzeichnet sein, dass es auf sich selbst als nächstes Element verweist.
rdf:langString
rdf:langString
List Ranking
rdf:langString
List ranking
xsd:integer
5748735
xsd:integer
950933817
rdf:langString
List Ranking bezeichnet die Aufgabe, den Elementen einer verketteten Liste ihren Rang innerhalb der Liste zuzuordnen. Der Rang eines Listenelements ist dabei definiert als der Abstand zum letzten Listenelement. Das Ermitteln der Ränge ist notwendig, um Listen ohne den Verlust der Reihenfolge der Listenelemente in Arrays umzuwandeln, auf denen viele parallele Operationen effizienter ausgeführt werden können. Der sequentielle Algorithmus zur Lösung der Aufgabe ist trivial mit einem Aufwand in , parallele Algorithmen dagegen sind deutlich komplexer und schwieriger zu implementieren, erreichen dafür aber Laufzeiten von , wie beispielsweise der in diesem Artikel vorgestellte Independent-Set-Removal-Algorithmus. Dieser Artikel beschränkt sich auf einfach verkettete Listen, außerdem soll das letzte Element einer Liste dadurch gekennzeichnet sein, dass es auf sich selbst als nächstes Element verweist.
rdf:langString
In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
xsd:nonNegativeInteger
3610