ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 11 Issue 3, January 2015

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

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