Kayaturan, Gokce Caylak and Vernitski, Alexei (2018) Encoding shortest paths in graphs assuming the code is queried using bit-wise comparison. Working Paper. Arxiv. (Unpublished)
Kayaturan, Gokce Caylak and Vernitski, Alexei (2018) Encoding shortest paths in graphs assuming the code is queried using bit-wise comparison. Working Paper. Arxiv. (Unpublished)
Kayaturan, Gokce Caylak and Vernitski, Alexei (2018) Encoding shortest paths in graphs assuming the code is queried using bit-wise comparison. Working Paper. Arxiv. (Unpublished)
Abstract
One model of message delivery in a computer network is based on labelling each edge by a subset of a (reasonably small) universal set, and then encoding a path as the union of the labels of its edges. Earlier work suggested using random edge labels, and that approach has a disadvantage of producing errors (false positives). We demonstrate that if we make an assumption about the shape of the network (in this paper we consider networks with a dense core and a tree-like periphery) and assume that messages are delivered along shortest paths, we can label edges in a way which prevents any false positives.
Item Type: | Monograph (Working Paper) |
---|---|
Uncontrolled Keywords: | math.CO |
Subjects: | Q Science > QA Mathematics |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 03 Jan 2019 12:45 |
Last Modified: | 16 May 2024 19:28 |
URI: | http://repository.essex.ac.uk/id/eprint/23708 |
Available files
Filename: 1806.09442v1.pdf