Search ACM DL

Search Issue

enter search term and/or author name

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

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