enter search term and/or author name
Generating rooted and free plane trees
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
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
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
Let G = (V, E) be an undirected graph, with three numbers d0(e) ≥ d1(e) ≥ d2(e) ≥ 0 for each edge e ∈ E. A solution is...
Online scheduling of splittable tasks
Leah Epstein, Rob Van Stee
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
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
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...