New Results on Hashing, Labeling Schemes and Algorithms
Publikation: Bog/antologi/afhandling/rapport › Ph.d.-afhandling › Forskning
In this thesis, we show several new results on hashing, labeling schemes and algorithms. There is not space in the abstract to mention all the results, but a result from each area is highlighted:
Linear hashing: We consider the classic hash function h(x) = ((ax+b) mod p) mod n, where a,b are chosen uniformly at random from {0,1,2,...,p-1}. We prove that when using h in hashing with chaining the expected size of the longest chain is, which is the first improvement on the folklore bound of . Appeared in [FOCS'16].
Adjacency labeling for trees: We show that there exists an induced universal graph with O(n) nodes for the family of forests on n nodes. We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich [STOC'88], Chung [J. of Graph Theory'90], Fraigniaud and Korman [SODA'10]. Joint work with Alstrup and Dahlgaard [FOCS'15].
Even cycle detection: For any constant k we give an algorithm that in time determines if a graph with m edges contains a cycle of length 2k. This improves upon a result by Yuster and Zwick [J. Discrete Math 1997] who gave an algorithm for this problem and noted that it is "plausible to conjecture that is the best possible bound in terms of n", where n is the number of nodes in the graph. If this conjecture is true, then our result is optimal in terms of n and m. Joint work with Dahlgaard and Stöckel [STOC'17].
Originalsprog | Engelsk |
---|
Forlag | Department of Computer Science, Faculty of Science, University of Copenhagen |
---|---|
Antal sider | 349 |
Status | Udgivet - 2017 |
ID: 183188264