enter search term and/or author name
Individual displacements for linear probing hashing with different insertion policies
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
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
Kristian De Lichtenberg, Stephen Alstrup, Mikkel Thorup, Jacob Holm
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
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...
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
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
Serge Plotkin, Adam Meyerson, Ashish Goel
This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. . We define α-supermajorization as an approximate form of vector majorization, and show...
The greedy algorithm for the minimum common string partition problem
Jiří Sgall, Marek Chrobak, Petr Kolman
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...