Abstract
With ever increasing size of graphs, many distributed graph systems emerged to store, preprocess and analyze them. While such systems ease up congestion on servers, they incur certain penalties compared to centralized data structure. First, the total storage required to store a graph in a distributed fashion increases. Second, attempting to answer queries on vertices of a graph stored in a distributed fashion can be significantly more complicated.
In order to lay theoretical foundations to the first penalty mentioned a large body of work concentrated on labeling schemes. A labeling scheme is a method of distributing the information about the structure of a graph among its vertices by assigning short labels, such that a selected function on vertices can be computed using only their labels. Using labeling schemes, specific queries can be determined using little communication and good running times, effectively eliminating the second penalty mentioned.
We continue this theoretical study in several ways. First, we dedicate a large part of the thesis to the graph family of trees, for which we provide an overview of labeling schemes supporting several important functions such as ancestry, routing and especially adjacency. The survey is complemented by novel contributions to this study, among which are the first asymptotically optimal adjacency labeling scheme for bounded degree trees, improved bounds on ancestry labeling schemes, dynamic multifunctional labeling schemes and an experimental evaluation of fully dynamic labeling schemes.
Due to a connection between adjacency labeling schemes and the graph theoretical study of induced universal graphs, we study these in depth and show novel results for bounded degree graphs and power-law graphs. We also survey and make progress on the related implicit representation conjecture. Finally, we extend the concept of labeling schemes to allow for a better understanding of the space cost incurred by information dissemination.
In order to lay theoretical foundations to the first penalty mentioned a large body of work concentrated on labeling schemes. A labeling scheme is a method of distributing the information about the structure of a graph among its vertices by assigning short labels, such that a selected function on vertices can be computed using only their labels. Using labeling schemes, specific queries can be determined using little communication and good running times, effectively eliminating the second penalty mentioned.
We continue this theoretical study in several ways. First, we dedicate a large part of the thesis to the graph family of trees, for which we provide an overview of labeling schemes supporting several important functions such as ancestry, routing and especially adjacency. The survey is complemented by novel contributions to this study, among which are the first asymptotically optimal adjacency labeling scheme for bounded degree trees, improved bounds on ancestry labeling schemes, dynamic multifunctional labeling schemes and an experimental evaluation of fully dynamic labeling schemes.
Due to a connection between adjacency labeling schemes and the graph theoretical study of induced universal graphs, we study these in depth and show novel results for bounded degree graphs and power-law graphs. We also survey and make progress on the related implicit representation conjecture. Finally, we extend the concept of labeling schemes to allow for a better understanding of the space cost incurred by information dissemination.
| Original language | English |
|---|
| Publisher | Department of Computer Science, Faculty of Science, University of Copenhagen |
|---|---|
| Publication status | Published - 2016 |