Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-79527-6_18 | SIROCCO |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aviv Bar-Natan | 1 | 0 | 0.34 |
| Panagiotis Charalampopoulos | 2 | 1 | 2.04 |
| Paweł Gawrychowski | 3 | 0 | 2.70 |
| Shay Mozes | 4 | 1 | 1.70 |
| Oren Weimann | 5 | 1 | 0.68 |