@inproceedings{525a9aed0da44e2d80e50eb41854863f,
title = "Compact oblivious routing in weighted graphs",
abstract = "The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of results that show tradeoffs between stretch and required size for the routing tables. This paper designs compact routing schemes for the cost-measure congestion, where the goal is to minimize the maximum relative load of a link in the network (the relative load of a link is its traffic divided by its bandwidth). We show that for arbitrary undirected graphs we can obtain oblivious routing strategies with competitive ratio {\~O}(1) that have header length {\~O}(1), label size {\~O}(1), and require routing-tables of size {\~O}(deg(v)) at each vertex v in the graph. This improves a result of R{\"a}cke and Schmid who proved a similar result in unweighted graphs.",
keywords = "Compact Routing, Competitive Analysis, Oblivious Routing",
author = "Philipp Czerner and Harald R{\"a}cke",
note = "Publisher Copyright: {\textcopyright} Philipp Czerner and Harald R{\"a}cke; 28th Annual European Symposium on Algorithms, ESA 2020 ; Conference date: 07-09-2020 Through 09-09-2020",
year = "2020",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.ESA.2020.36",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Fabrizio Grandoni and Grzegorz Herman and Peter Sanders",
booktitle = "28th Annual European Symposium on Algorithms, ESA 2020",
}