Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 7 Issue 1, November 2010

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(n5/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 B1, …,Bk 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...