Search ACM DL

Search Issue

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

DOI: 10.1145/2684068

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

DOI: 10.1145/2651421

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...

**Time Complexity of Link Reversal Routing**

Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch, Josef Widder

Article No.: 18

DOI: 10.1145/2644815

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

DOI: 10.1145/2629654

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**

Artur Jeż

Article No.: 20

DOI: 10.1145/2631920

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...

**Interval Deletion Is Fixed-Parameter Tractable**

Yixin Cao, Dániel Marx

Article No.: 21

DOI: 10.1145/2629595

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 10* ^{k}*...

**Average Case and Distributional Analysis of Dual-Pivot Quicksort**

Sebastian Wild, Markus E. Nebel, Ralph Neininger

Article No.: 22

DOI: 10.1145/2629340

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...

**Minimum Makespan Multi-Vehicle Dial-a-Ride**

Inge Li Gørtz, Viswanath Nagarajan, R. Ravi

Article No.: 23

DOI: 10.1145/2629653

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

DOI: 10.1145/2629508

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...