Search ACM DL

Search Issue

enter search term and/or author name

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

**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{*m*^{3/2}log*n*, *m*^{3/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/3*n*^{1 −...
}

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