Search ACM DL

Search Issue

enter search term and/or author name

**Generating rooted and free plane trees**

Joe Sawada

Pages: 1-13

DOI: 10.1145/1125994.1125995

This article has two main results. First, we develop a simple algorithm to list all nonisomorphic rooted plane trees in lexicographic order using a level sequence representation. Then, by selecting a unique centroid to act as the root of a free plane...

**Finding 3-shredders efficiently**

Rajneesh Hegde

Pages: 14-43

DOI: 10.1145/1125994.1125996

A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional...

**Pattern matching for arc-annotated sequences**

Jens Gramm, Jiong Guo, Rolf Niedermeier

Pages: 44-65

DOI: 10.1145/1125994.1125997

We study pattern matching for arc-annotated sequences. An *O*(*nm*) time algorithm is given for the problem to determine whether a length *m* sequence with nested arc annotation is an arc-preserving subsequence (aps) of a length...

**The minimum generalized vertex cover problem**

Refael Hassin, Asaf Levin

Pages: 66-78

DOI: 10.1145/1125994.1125998

Let *G* = (*V*, *E*) be an undirected graph, with three numbers *d*_{0}(*e*) ≥ *d*_{1}(*e*) ≥ *d*_{2}(*e*) ≥ 0 for each edge *e* ∈ *E*. A solution is...

**Online scheduling of splittable tasks**

Leah Epstein, Rob Van Stee

Pages: 79-94

DOI: 10.1145/1125994.1125999

We consider online scheduling of splittable tasks on parallel machines, where the goal is to minimize the last completion time (the makespan). In our model, each task can be split into a limited number of parts, that can then be scheduled...

**Minimizing total completion time on uniform machines with deadline constraints**

Teofilo F. Gonzalez, Joseph Y.-T. Leung, Michael Pinedo

Pages: 95-115

DOI: 10.1145/1125994.1126000

Consider *n* independent jobs and *m* uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time *t* = 0. Job *j* must complete its processing before or...

**Improved results for data migration and open shop scheduling**

Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai

Pages: 116-129

DOI: 10.1145/1125994.1126001

The *data migration* problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage...

**Problems column**

Samir Khuller

Pages: 130-134

DOI: 10.1145/1125994.1126002