Search ACM DL

Search Issue

enter search term and/or author name

**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(n^{3}) Time**

Qian-Ping Gu, Hisao Tamaki

Article No.: 30

DOI: 10.1145/1367064.1367070

We give an *O*(*n*^{3}) 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...
*