Research Repository

Encoding shortest paths in graphs assuming the code is queried using bit-wise comparison

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)

[img]
Preview
Text
1806.09442v1.pdf

Download (847kB) | Preview

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, math.CO
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 03 Jan 2019 12:45
Last Modified: 03 Jan 2019 13:15
URI: http://repository.essex.ac.uk/id/eprint/23708

Actions (login required)

View Item View Item