Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 1 Issue 2, October 2005

Individual displacements for linear probing hashing with different insertion policies
Svante Janson
Pages: 177-213
DOI: 10.1145/1103963.1103964
We study the distribution of the individual displacements in hashing with linear probing for three different versions: First Come, Last Come and Robin Hood. Asymptotic distributions and their moments are found when the the size of the hash table...

Exact distribution of individual displacements in linear probing hashing
Alfredo Viola
Pages: 214-242
DOI: 10.1145/1103963.1103965
This paper studies the distribution of individual displacements for the standard and the Robin Hood linear probing hashing algorithms. When the a table of size m has n elements, the distribution of the search cost of a random element is...

Maintaining information in fully dynamic trees with top trees
Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, Mikkel Thorup
Pages: 243-264
DOI: 10.1145/1103963.1103966
We design top trees as a new simpler interface for data structures maintaining information in a fully dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the...

Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
Raja Jothi, Balaji Raghavachari
Pages: 265-282
DOI: 10.1145/1103963.1103967

Given an undirected graph G = (V,E) with nonnegative costs on its edges, a root node r V, a set of demands D V with demand v D wishing to route w(v) units of flow (weight) to...

Computing almost shortest paths
Michael Elkin
Pages: 283-323
DOI: 10.1145/1103963.1103968

We study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-ASP</i>) problem. Given an unweighted graph <i>G</i> &equals; (<i>V,E</i>), and a subset <i>S</i> &sube;...

An O(VE) algorithm for ear decompositions of matching-covered graphs
Marcelo H. De Carvalho, joseph cheriyan
Pages: 324-337
DOI: 10.1145/1103963.1103969
Our main result is an O(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where n and m denote the number of nodes and edges. The improvement in the running time comes from new...

Approximate majorization and fair online load balancing
Ashish Goel, Adam Meyerson, Serge Plotkin
Pages: 338-349
DOI: 10.1145/1103963.1103970
This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. [1929]. We define α-supermajorization as an approximate form of vector majorization, and show...

The greedy algorithm for the minimum common string partition problem
Marek Chrobak, Petr Kolman, Jiří Sgall
Pages: 350-366
DOI: 10.1145/1103963.1103971
In the Minimum Common String Partition problem (MCSP), we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. This problem is NP-hard, even...