4 papers
Multi-Queues Can Be State-of-the-Art Priority Schedulers
Anastasiia Postnikova, Nikita Koval, Giorgi Nadiradze +1
Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given threads and disti…
A Scalable Concurrent Algorithm for Dynamic Connectivity
Alexander Fedorov, Nikita Koval, Dan Alistarh
Dynamic Connectivity is a fundamental algorithmic graph problem, motivated by a wide range of applications to social and communication networks and used as a building block in vari…
Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers
Dan Alistarh, Nikita Koval, Giorgi Nadiradze
Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared…
In Search of the Fastest Concurrent Union-Find Algorithm
Dan Alistarh, Alexander Fedorov, Nikita Koval
Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequenti…