enter search term and/or author name
A loopless Gray code for rooted trees
James Korsh, Paul Lafollette
Beyer and Hedetniemi  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
This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σm that satisfies a given set of k-wise demands. For every...
Bipartite roots of graphs
Lap Chi Lau
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  proved the...
Efficient algorithms for bichromatic separability
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun
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
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
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
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
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...