Search ACM DL

Search Issue

enter search term and/or author name

**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> = (<i>V,E</i>), and a subset <i>S</i> ⊆...

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

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