5 citations · 8 across the 6 of their papers we have counts for
7 papers
Certifying Induced Subgraphs in Large Graphs
Ulrich Meyer, Hung Tran, Konstantinos Tsakalidis
We introduce I/O-optimal certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input g…
Succinct Permutation Graphs
Konstantinos Tsakalidis, Sebastian Wild, Viktor Zamaraev
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms.…
Cache-Oblivious Priority Queues with Decrease-Key and Applications to Graph Algorithms
John Iacono, Riko Jacob, Konstantinos Tsakalidis
We present priority queues in the cache-oblivious external memory model with block size and main memory size that support on elements, operation \textsc{UPDATE} (combin…
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d
Timothy M. Chan, Yakov Nekrich, Saladi Rahul +1
In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. -We give the first…
I/O-Efficient Planar Range Skyline and Attrition Priority Queues
Casper Kejlberg-Rasmussen, Yufei Tao, Konstantinos Tsakalidis +2
In the planar range skyline reporting problem, we store a set P of n 2D points in a structure such that, given a query rectangle Q = [a_1, a_2] x [b_1, b_2], the maxima (a.k.a. sky…
I/O-Efficient Dynamic Planar Range Skyline Queries
Casper Kejlberg-Rasmussen, Konstantinos Tsakalidis, Kostas Tsichlas
We present the first fully dynamic worst case I/O-efficient data structures that support planar orthogonal \textit{3-sided range skyline reporting queries} in $\bigO (\log_{2B^ε} n…
Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time
Gerth Stølting Brodal, Alexis C. Kaporis, Apostolos N. Papadopoulos +3
This work studies the problem of 2-dimensional searching for the 3-sided range query of the form in both main and external memory, by considering a vari…