Browse Proceedings

We show that most algorithms from the literature on listing the triangles of a graph have a common abstraction. Our unifying framework highlights that these seemingly different algorithms are in fact instantiations of a single generic procedure, and ...

In this paper we present an experimental evaluation of the algorithms by Brodal et al. [SODA 2013] for computing the triplet and quartet distance measures between two leaf labelled rooted and unrooted trees of arbitrary degree, respectively. The ...

We present the first I/O- and practically-efficient algorithm for simplifying a planar subdivision, such that no point is moved more than a given distance ε_xy and such that neighbor relations between faces (homotopy) are preserved. Under some ...

Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically -- as long as the algorithm does not exhaust the ...

Given the user's input as a query, auto-completion selects the top-k strings with the highest scores from the strings matching the query in a dictionary. A recent study [14] proposed space-efficient data structures for top-k prefix matching for auto-...

The idea of multi-pivot quicksort has recently received the attention of researchers after Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior intuition, outperforms standard quicksort by a a significant margin under ...

The theory community has proposed several new heap variants in the recent past which have remained largely untested experimentally. We take the field back to the drawing board, with straightforward implementations of both classic and novel structures ...

The upward crossing number problem asks for a drawing of the graph into the plane with the minimum number of edge crossings where the edges are drawn as monotonously increasing curves w.r.t. the y-axis. While there is a large body of work on solving ...

We propose an algorithm for c-planarity testing which is correct and efficient, but not, in general, complete, i.e., there are input instances on which the algorithm declines to give an answer. At the core of this algorithm is an algebraic criterion ...

Typically in a scheduling problem we are given jobs of different processing times p_j and different priority weights w_j, and need to schedule them on a single machine in order to minimize a specific cost function. In this paper we consider the non-linear ...

Computational knot theory and 3-manifold topology have seen significant breakthroughs in recent years, despite the fact that many key algorithms have complexity bounds that are exponential or greater. In this setting, experimentation is essential for ...

We study the problem of efficiently computing journeys in timetable networks. Our algorithm optimally answers profile queries, computing all journeys given a time interval. Our study demonstrates that queries can be answered optimally on large country-...

We consider the stochastic on-time arrival (SOTA) problem of finding the optimal routing strategy for reaching a given destination within a pre-specified time budget and provide the first results on using preprocessing techniques for speeding up the ...

We propose a new labeling method for shortest-path and distance queries on road networks. We present a new framework (i.e. data structure and query algorithm) referred to as highway-based labelings and a preprocessing algorithm for it named pruned ...

Public-transportation route-planning systems typically work as follows. The user specifies a source and a target location, as well as a departure time. The system then returns one or more optimal trips at or after that departure time. In this paper, we ...