SCIENCE@home

[RETRACTED: Concurrent Programming 2019: COURSE PROJECT 7]

Jeremy Mayeres,Charles R. Newton,Helena Arpudaraj

Published 2019 in Unknown venue

ABSTRACT

This paper introduces a lock-free version of a Pairing heap. Dijkstra’s algorithm is a search algorithm to solve the single-source shortest path problem. The efficiency of Dijkstra’s al-gorithm is asymptoticly improved from O ( | V | 2 ) to O ( | E | + | V | log( | V | )) when an operation is available to decrease the recorded distance of a vertex to the target source in constant time ( decreaseKey .) The performance of Dijkstra’s algo-rithm also improves when threads can also perform work concurrently (in particular, when decreaseKey calls occur concurrently.) However, current implementations of de-creaseKey on popular backing data structures such as Pairing heaps and Fibonacci heaps severely limit concurrency. Lock-free techniques can improve the concurrency of search structures such as heaps. In this paper we introduce de-creaseKey and insert operators for Pairing heaps that provide lock-free guarantees while still running in constant time. Techniques for parallelizing Dijkstra’s algorithm are additionally discussed.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-61 of 61 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1