enter search term and/or author name
Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen
Article No.: 16
For an undirected n-vertex planar graph G with nonnegative edge weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We...
Maximizing the Minimum Load for Random Processing Times
Stefanie Gerke, Konstantinos Panagiotou, Justus Schwartz, Angelika Steger
Article No.: 17
In this article, we consider a stochastic variant of the so-called Santa Claus problem. The Santa Claus problem is equivalent to the problem of scheduling a set of n jobs on m parallel machines without preemption, so as to...
Link reversal is a versatile algorithm design paradigm, originally proposed by Gafni and Bertsekas in 1981 for routing and subsequently applied to other problems including mutual exclusion, leader election, and resource allocation. Although these...
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Glencora Borradaile, Philip N. Klein, Claire Mathieu
Article No.: 19
We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ε > 0 and given n terminals in the plane with connection requests between some...
Faster Fully Compressed Pattern Matching by Recompression
Article No.: 20
In this article, a fully compressed pattern matching problem is studied. The compression is represented by straight-line programs (SLPs)—that is, context-free grammars generating exactly one string; the term fully means that both the...
We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10k...
Average Case and Distributional Analysis of Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel, Ralph Neininger
Article No.: 22
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's...
Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs...
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
Reut Levi, Dana Ron
Article No.: 24
Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient partition oracles. A partition oracle is a procedure that, given access to the incidence lists representation of a...