32 citations · 50 across the 13 of their papers we have counts for
16 papers
Succinct Representation of Search Trees on Trees
Seungbum Jo, Nodari Sitchinava
A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where t…
The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
Peyman Afshani, Gerth Stølting Brodal, Nodari Sitchinava
We prove that no deterministic output-sensitive algorithm for the planar convex hull and maxima problems can obtain both optimal time and I/O complexity, where the optimality is de…
Efficient Parallel Algorithms for Hypergraph Matching
Henrik Reinstädtler, Christian Schulz, Nodari Sitchinava +1
We present efficient parallel algorithms for computing maximal matchings in hypergraphs. Our algorithm finds locally maximal edges in the hypergraph and adds them in parallel to th…
LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank of "europar" amongst the strings "eureka", "eurasia…
A parallel priority queue with fast updates for GPU architectures
Kyle Berney, John Iacono, Ben Karsin +1
The single-source shortest path (SSSP) problem is a well-studied problem that is used in many applications. In the parallel setting, a work-efficient algorithm that additionally at…
Locality
Peyman Afshani, John Iacono, Varunkumar Jayapaul +2
The program performance on modern hardware is characterized by \emph{locality of reference}, that is, it is faster to access data that is close in address space to data that has be…