Name
Abstract | ||
|---|---|---|
A k-uniform hypergraph H = (V, E) is called l-orientable, if there is an assignment of each edge e ε E to one of its vertices v ε e such that no vertex is assigned more than l edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the l-orientability of Hn,m,k for all k ≥ 3 and l ≥ 1, i.e., we determine a critical quantity c*k,l such that with probability 1 − o(1) the graph Hn,cn,k has an l-orientation if c c*k,l, but fails doing so if c c*k,l. Our result has various applications including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1017/S0963548315000334 | Combinatorics, Probability & Computing |
Keywords | DocType | Volume |
guaranteed maximum load,multiple-orientability threshold,sharp load threshold,load balancing,graph hn,hard disk array,l edge,k-uniform hypergraphs,k-uniform hypergraph h,critical quantity,vertices v,random hypergraphs,distributed computing,disk array,leader election,load balance,randomized algorithms | Journal | 25 |
Issue | ISSN | ISBN |
6 | 0963-5483 | 978-1-61197-251-1 |
Citations | PageRank | References |
9 | 0.68 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikolaos Fountoulakis | 1 | 185 | 18.04 |
| Megha Khosla | 2 | 18 | 6.01 |
| Konstantinos Panagiotou | 3 | 290 | 27.80 |