ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 4 Issue 3, June 2008

Optimality of an algorithm solving the Bottleneck Tower of Hanoi problem
Yefim Dinitz, Shay Solomon
Article No.: 25
DOI: 10.1145/1367064.1367065

We study the Bottleneck Tower of Hanoi puzzle posed by D. Wood in 1981. There, a relaxed placement rule allows a larger disk to be placed higher than a smaller one if their size difference is less than a pregiven value k. A shortest...

Determining plurality
Laurent Alonso, Edward M. Reingold
Article No.: 26
DOI: 10.1145/1367064.1367066

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that (c...

Average-case lower bounds for the plurality problem
Laurent Alonso, Edward M. Reingold
Article No.: 27
DOI: 10.1145/1367064.1367067

Given a set of n elements, each of which is colored one of c ≥ 2 colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower...

Balanced parentheses strike back
Hsueh-I Lu, Chia-Chi Yeh
Article No.: 28
DOI: 10.1145/1367064.1367068

An ordinal tree is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The best previously known result is due to Geary...

Roundtrip spanners and roundtrip routing in directed graphs
Iam Roditty, Mikkel Thorup, Uri Zwick
Article No.: 29
DOI: 10.1145/1367064.1367069

We introduce the notion of roundtrip-spanners of weighted directed graphs and describe efficient algorithms for their construction. We show that for every integer k ≥ 1 and any ε > 0, any directed graph on n...

Optimal branch-decomposition of planar graphs in O(n3) Time
Qian-Ping Gu, Hisao Tamaki
Article No.: 30
DOI: 10.1145/1367064.1367070

We give an O(n3) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. This is achieved through a refinement to the previously best known algorithm of Seymour...

Testing Euclidean minimum spanning trees in the plane
Artur Czumaj, Christian Sohler
Article No.: 31
DOI: 10.1145/1367064.1367071

Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than ε n...

Dynamic entropy-compressed sequences and full-text indexes
Veli Mäkinen, Gonzalo Navarro
Article No.: 32
DOI: 10.1145/1367064.1367072

We give new solutions to the Searchable Partial Sums with Indels problem. Given a sequence of n k-bit numbers, we present a structure taking kn + o(kn) bits of space, able of performing operations sum,...

Writing-all deterministically and optimally using a nontrivial number of asynchronous processors
Dariusz R. Kowalski, Alexander A. Shvartsman
Article No.: 33
DOI: 10.1145/1367064.1367073

The problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. This article considers an abstraction of this problem called Write-All: using p processors write 1's into...

Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon (Moni) Shahar, Maxim Sviridenko
Article No.: 34
DOI: 10.1145/1367064.1367074

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the...

Clustering, community partition and disjoint spanning trees
Cun-Quan Zhang, Yongbin Ou
Article No.: 35
DOI: 10.1145/1367064.1367075

Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as...

Improved algorithms for the minmax-regret 1-center and 1-median problems
Hung-I. Yu, Tzu-Chin Lin, Biing-Feng Wang
Article No.: 36
DOI: 10.1145/1367064.1367076

In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the...

Compact name-independent routing with minimum stretch
Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, Mikkel Thorup
Article No.: 37
DOI: 10.1145/1367064.1367077

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using aÕ(&sqrt;n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the...

Getting the best response for your erg
Kirk Pruhs, Patchrawat Uthaisombut, Gerhard Woeginger
Article No.: 38
DOI: 10.1145/1367064.1367078

We consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint A on energy used. We propose an algorithmic approach in which an energy optimal schedule is...