Search ACM DL

Search Issue

enter search term and/or author name

**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...
*