4 citations · 13 across the 20 of their papers we have counts for
5 papers · 1 filter
Maximum Scatter TSP in Doubling Metrics
László Kozma, Tobias Mömke
We study the problem of finding a tour of points in which every edge is long. More precisely, we wish to find a tour that visits every point exactly once, maximizing the length…
Hitting Set for hypergraphs of low VC-dimension
Karl Bringmann, László Kozma, Shay Moran +1
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized co…
Pattern-avoiding access in binary search trees
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST…
Greedy Is an Almost Optimal Deque
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this…
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs)…