Fault-Tolerant Distance Labeling for Planar Graphs
| Autor: | Paweł Gawrychowski, Aviv Bar-Natan, Oren Weimann, Panagiotis Charalampopoulos, Shay Mozes |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Structural Information and Communication Complexity ISBN: 9783030795269 SIROCCO |
| DOI: | 10.1007/978-3-030-79527-6_18 |
| Popis: | In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph G such that from the labels of any three vertices u, v, f we can infer the u-to-v distance in the graph \(G\setminus \{f\}\). We show that any directed weighted planar graph (and in fact any graph in a graph family with \(O(\sqrt{n})\)-size separators, such as minor-free graphs) admits fault-tolerant distance labels of size \(O(n^{2/3})\). We extend these labels in a way that allows us to also count the number of shortest paths, and provide additional upper and lower bounds for labels and oracles for counting shortest paths. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|