ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 2 Issue 2, April 2006

A loopless Gray code for rooted trees
James Korsh, Paul Lafollette
Pages: 135-152
DOI: 10.1145/1150334.1150335
Beyer and Hedetniemi [1980] gave the first constant average-time algorithm for the generation of all rooted trees with n nodes. This article presents the first combinatorial Gray code for these trees and a loopless algorithm for its...

Algorithmic construction of sets for k-restrictions
Noga Alon, Dana Moshkovitz, Shmuel Safra
Pages: 153-177
DOI: 10.1145/1150334.1150336
This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σm that satisfies a given set of k-wise demands. For every...

Bipartite roots of graphs
Lap Chi Lau
Pages: 178-208
DOI: 10.1145/1150334.1150337
Graph H is a root of graph G if there exists a positive integer k such that x and y are adjacent in G if and only if their distance in H is at most k. Motwani and Sudan [1994] proved the...

Efficient algorithms for bichromatic separability
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun
Pages: 209-227
DOI: 10.1145/1150334.1150338
A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding whether two sets of n points in...

This side up!
Leah Epstein, Rob van Stee
Pages: 228-243
DOI: 10.1145/1150334.1150339
We consider two- and three-dimensional bin-packing problems where 90° rotations are allowed. We improve all known asymptotic performance bounds for these problems. In particular, we show how to combine ideas from strip packing and two-dimensional...

Minimizing mean flow time for UET tasks
Yumei Huo, Joseph Y.-T. Leung
Pages: 244-262
DOI: 10.1145/1150334.1150340
We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman--Graham...

Robust subgraphs for trees and paths
Refael Hassin, Danny Segev
Pages: 263-281
DOI: 10.1145/1150334.1150341
Consider a graph problem which is associated with a parameter, for example, that of finding a longest tour spanning k vertices. The following question is natural: Is there a small subgraph that contains an optimal or near optimal solution for...

An improved algorithm for CIOQ switches
Yossi Azar, Yossi Richter
Pages: 282-295
DOI: 10.1145/1150334.1150342
The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and...