ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


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

The cyclic multi-peg Tower of Hanoi
Daniel Berend, Amir Sapir
Pages: 297-317
DOI: 10.1145/1159892.1159893
Variants of the classical Tower of Hanoi problem evolved in various directions. Allowing more than 3 pegs, and imposing limitations on the possible moves among the pegs, are two of these. Here, we deal with the case of h≥3 pegs arranged on...

The register function for t-ary trees
Michael Drmota, Helmut Prodinger
Pages: 318-334
DOI: 10.1145/1159892.1159894
For the register function for t-ary trees, recently introduced by Auber et al., we prove that the average is log4n + O(1), if all such trees with n internal nodes are considered to be equally likely.This...

Oracles for bounded-length shortest paths in planar graphs
Lukasz Kowalik, Maciej Kurowski
Pages: 335-363
DOI: 10.1145/1159892.1159895
We present a new approach for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G = (V, E), one can build in O(|V|) time a data structure,...

Online topological ordering
Irit Katriel, Hans L. Bodlaender
Pages: 364-379
DOI: 10.1145/1159892.1159896
It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O(min{m3/2logn, m3/2 +...

Optimal constrained graph exploration
Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar
Pages: 380-402
DOI: 10.1145/1159892.1159897
We address the problem of constrained exploration of an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter...

Faster fixed parameter tractable algorithms for finding feedback vertex sets
Venkatesh Raman, Saket Saurabh, C. R. Subramanian
Pages: 403-415
DOI: 10.1145/1159892.1159898
A feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n1 −...

An approximation algorithm for scheduling malleable tasks under general precedence constraints
Klaus Jansen, Hu Zhang
Pages: 416-434
DOI: 10.1145/1159892.1159899
In this article, we study the problem of scheduling malleable tasks with precedence constraints. We are given m identical processors and n tasks. For each task the processing time is a function of the number of processors allotted to...

Secure multiparty computation of approximations
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright
Pages: 435-472
DOI: 10.1145/1159892.1159900
Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be...

The NP-completeness column: The many limits on approximation
David S. Johnson
Pages: 473-489
DOI: 10.1145/1159892.1159901
This is the 25th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book Computers and Intractability: A Guide to the Theory of...