Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 5 Issue 2, March 2009

Testing bipartiteness of geometric intersection graphs
David Eppstein
Article No.: 15
DOI: 10.1145/1497290.1497291

We show how to test the bipartiteness of an intersection graph of n line segments or simple polygons in the plane, or of an intersection graph of balls in d-dimensional Euclidean space, in time O(n log n). More...

Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
Ke Chen, Haim Kaplan, Micha Sharir
Article No.: 16
DOI: 10.1145/1497290.1497292

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use...

Average-case analysis of some plurality algorithms
Laurent Alonso, Edward M. Reingold
Article No.: 17
DOI: 10.1145/1497290.1497293

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected...

Throughput maximization of real-time scheduling with batching
Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph (Seffi) Naor, Baruch Schieber, Hadas Shachnai
Article No.: 18
DOI: 10.1145/1497290.1497294

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel...

Bicriteria approximation tradeoff for the node-cost budget problem
Yuval Rabani, Gabriel Scalosub
Article No.: 19
DOI: 10.1145/1497290.1497295

We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given...

A polynomial-time approximation scheme for embedding hypergraph in a cycle
Guojun Li, Xiaotie Deng, Ying Xu
Article No.: 20
DOI: 10.1145/1497290.1497296

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion, namely the maximum number of paths that use any single edge in a cycle, is minimized.

The minimum congestion hypergraph...

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov
Article No.: 21
DOI: 10.1145/1497290.1497297

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, E) and an edge set E on V disjoint to E, find a minimum-size subset of edges F...

Approximating the distance to properties in bounded-degree and general sparse graphs
Sharon Marko, Dana Ron
Article No.: 22
DOI: 10.1145/1497290.1497298

We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property P. That is, we are interested in sublinear algorithms for estimating the fraction of edge...

Linear time 3-approximation for the MAST problem
Vincent Berry, Christophe Paul, Sylvain Guillemot, François Nicolas
Article No.: 23
DOI: 10.1145/1497290.1497299

Given a set of leaf-labeled trees with identical leaf sets, the well-known Maximum Agreement SubTree (MAST) problem consists in finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its...

Algorithms for distributional and adversarial pipelined filter ordering problems
Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu
Article No.: 24
DOI: 10.1145/1497290.1497300

Pipelined filter ordering is a central problem in database query optimization. The problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as...