Maintaining Acyclicity of Concurrent Graphs

Sathya Peri Muktikanta Sa Nandini Singhal
Abstract: In this paper, we consider the problem of preserving acyclicity in a directed graph (for shared memory architecture) that is concurrently being updated by threads adding/deleting vertices and edges. To the best of our knowledge, no previous paper has presented a concurrent graph data structure. We implement the concurrent directed graph data-structure as a concurrent adjacency list representation. We extend the lazy list implementation of concurrent linked lists for maintaining concurrent adjacency lists. There ...