Search ACM DL

Search Issue

enter search term and/or author name

**Computing large matchings fast**

Ignaz Rutter, Alexander Wolff

Article No.: 1

DOI: 10.1145/1868237.1868238

In this article we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly...

**Approximation algorithms for the sex-equal stable marriage problem**

Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa

Article No.: 2

DOI: 10.1145/1868237.1868239

The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this...

**A faster algorithm for computing the girth of planar and bounded genus graphs**

Hristo N. Djidjev

Article No.: 3

DOI: 10.1145/1868237.1868240

The *girth* of a graph *G* is the length of a shortest cycle of *G*. In this article we design an *O*(*n*^{5/4} log *n*) algorithm for finding the girth of an undirected *n*-vertex planar graph, the first...

**Length-bounded cuts and flows**

Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondřej Pangrác, Heiko Schilling, Martin Skutella

Article No.: 4

DOI: 10.1145/1868237.1868241

For a given number *L*, an *L*-length-bounded edge-cut (node-cut, respectively) in a graph *G* with source *s* and sink *t* is a set *C* of edges (nodes, respectively) such that no *s*-*t*-path of length at...

**Additive spanners and (α, β)-spanners**

Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie

Article No.: 5

DOI: 10.1145/1868237.1868242

An (α, β)-spanner of an unweighted graph *G* is a subgraph *H* that distorts distances in *G* up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a...

**On the bicriteria k-server problem**

Michele Flammini, Gaia Nicosia

Article No.: 6

DOI: 10.1145/1868237.1868244

In this article we consider multicriteria formulations of classical online problems in which an algorithm must simultaneously perform well with respect to two different cost measures. Every strategy for serving a sequence of requests is...

**On the online unit clustering problem**

Leah Epstein, Rob Van Stee

Article No.: 7

DOI: 10.1145/1868237.1868245

We continue the study of the online unit clustering problem, introduced by Chan and Zarrabi-Zadeh (*Workshop on Approximation and Online Algorithms 2006*, LNCS 4368, p. 121--131. Springer, 2006). We design a deterministic algorithm with a...

**Clustering lines in high-dimensional space**: Classification of incomplete data

Jie Gao, Michael Langberg, Leonard J. Schulman

Article No.: 8

DOI: 10.1145/1868237.1868246

A set of *k* balls *B*_{1}, …,*B*_{k} in a Euclidean space is said to cover a collection of lines if every line intersects some ball. We consider the *k*-*center problem for lines* in...

**Geodesic Fréchet distance inside a simple polygon**

Atlas F. Cook IV, Carola Wenk

Article No.: 9

DOI: 10.1145/1868237.1868247

We present an alternative to parametric search that applies to both the nongeodesic and geodesic Fréchet optimization problems. This randomized approach is based on a variant of red-blue intersections and is appealing due to its elegance...

**The compressed permuterm index**

Paolo Ferragina, Rossano Venturini

Article No.: 10

DOI: 10.1145/1868237.1868248

The *Permuterm index* [Garfield 1976] is a time-efficient and elegant solution to the string dictionary problem in which pattern queries may possibly include one wild-card symbol (called *Tolerant Retrieval* problem)....

**I/O-efficient batched union-find and its applications to terrain analysis**

Pankaj K. Agarwal, Lars Arge, Ke Yi

Article No.: 11

DOI: 10.1145/1868237.1868249

In this article we present an I/O-efficient algorithm for the batched (off-line) version of the union-find problem. Given any sequence of *N* union and find operations, where each union operation joins two distinct sets, our algorithm uses...

**How to probe for an extreme value**

Ashish Goel, Sudipto Guha, Kamesh Munagala

Article No.: 12

DOI: 10.1145/1868237.1868250

In several systems applications, parameters such as load are known only with some associated uncertainty, which is specified, or modeled, as a distribution over values. The performance of the system optimization and monitoring schemes can be...

**Taxes for linear atomic congestion games**

Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos

Article No.: 13

DOI: 10.1145/1868237.1868251

We study congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non--cooperative and...