enter search term and/or author name
Testing bipartiteness of geometric intersection graphs
Article No.: 15
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
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
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...
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
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
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
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
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...
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
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...