20 citations · 97 across the 21 of their papers we have counts for
25 papers
Multiway Powersort
William Cawley Gelling, Markus E. Nebel, Benjamin Smith +1
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This build…
Towards the 5/6-Density Conjecture of Pinwheel Scheduling
Leszek Gąsieniec, Benjamin Smith, Sebastian Wild
Pinwheel Scheduling aims to find a perpetual schedule for unit-length tasks on a single machine subject to given maximal time spans (a.k.a. frequencies) between any two consecutive…
Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…
Succinct Euler-Tour Trees
Travis Gagie, Sebastian Wild
We show how a collection of Euler-tour trees for a forest on vertices can be stored in bits such that simple queries take constant time, more complex queries take…
Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima
J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner +1
We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources co…
Lazy Search Trees
Bryce Sandlund, Sebastian Wild
We introduce the lazy search tree data structure. The lazy search tree is a comparison-based data structure on the pointer machine that supports order-based operations such as rank…
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.…
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
Meng He, J. Ian Munro, Yakov Nekrich +2
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports…
Efficient Second-Order Shape-Constrained Function Fitting
David Durfee, Yu Gao, Anup B. Rao +1
We give an algorithm to compute a one-dimensional shape-constrained function that best fits given data in weighted- norm. We give a single algorithm that works for a va…
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space
J. Ian Munro, Sebastian Wild
The range-minimum query (RMQ) problem is a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal …
QuickXsort - A Fast Sorting Scheme in Theory and Practice
Stefan Edelkamp, Armin Weiß, Sebastian Wild
QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare's Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting a…
Sesquickselect: One and a half pivots for cache-efficient selection
Conrado Martínez, Markus Nebel, Sebastian Wild
Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in in…
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
J. Ian Munro, Sebastian Wild
We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with practically negligible overhead. Previo…
Average Cost of QuickXsort with Pivot Sampling
Sebastian Wild
QuickXsort is a strategy to combine Quicksort with another sorting method X, so that the result has essentially the same comparison cost as X in isolation, but sorts in place even…
Median-of-k Jumplists and Dangling-Min BSTs
Markus E. Nebel, Elisabeth Neumann, Sebastian Wild
We extend randomized jumplists introduced by Brönnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomiz…
Quicksort Is Optimal For Many Equal Keys
Sebastian Wild
I prove that the average number of comparisons for median-of- Quicksort (with fat-pivot a.k.a. three-way partitioning) is asymptotically only a constant times worse than t…
Why Is Dual-Pivot Quicksort Fast?
Sebastian Wild
I discuss the new dual-pivot Quicksort that is nowadays used to sort arrays of primitive types in Java. I sketch theoretical analyses of this algorithm that offer a possible, and i…
A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment
Raphael Reitzig, Sebastian Wild
Proportional apportionment is the problem of assigning seats to parties according to their relative share of votes. Divisor methods are the de-facto standard solution, used in many…
Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
Raphael Reitzig, Sebastian Wild
Given a set of n sticks of various (not necessarily different) lengths, what is the largest length so that we can cut k equally long pieces of this length from the given set of sti…
Analysis of Pivot Sampling in Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Conrado Martínez
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this a…
Analysis of Branch Misses in Quicksort
Conrado Martínez, Markus E. Nebel, Sebastian Wild
The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to qua…
Pivot Sampling in Dual-Pivot Quicksort
Markus E. Nebel, Sebastian Wild
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to…
Average Case Analysis of Java 7's Dual Pivot Quicksort
Sebastian Wild, Markus E. Nebel
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical…
Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
Sebastian Wild, Markus E. Nebel, Hosam Mahmoud
There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when…