Algorithms (TALG)


Search Issue
enter search term and/or author name


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

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 d0(e) ≥ d1(e) ≥ d2(e) ≥ 0 for each edge eE. A solution is...

Online scheduling of splittable tasks
Rob Van Stee, Leah Epstein
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, Michael Pinedo, Joseph Y.-T. Leung
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
Hadas Shachnai, Magnús M. Halldórsson, Guy Kortsarz, Rajiv Gandhi
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