Header

UZH-Logo

Maintenance Infos

Interval routing schemes for circular-arc graphs


Gurski, Frank; Poullie, Patrick (2017). Interval routing schemes for circular-arc graphs. International Journal of Foundations of Computer Science, 28(1):39-60.

Abstract

Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we outline an algorithm to calculate the routing scheme for circular-arc graphs in

Abstract

Interval routing is a space efficient method to realize a distributed routing function. In this paper we show that every circular-arc graph allows a shortest path strict 2-interval routing scheme, i.e., by introducing a global order on the vertices and assigning at most two (strict) intervals in this order to the ends of every edge allows to depict a routing function that implies exclusively shortest paths. Since circular-arc graphs do not allow shortest path 1-interval routing schemes in general, the result implies that the class of circular-arc graphs has strict compactness 2, which was a hitherto open question. Additionally, we show that the constructed 2-interval routing scheme is a 1-interval routing scheme with at most one additional interval assigned at each vertex and we outline an algorithm to calculate the routing scheme for circular-arc graphs in

Statistics

Altmetrics

Downloads

0 downloads since deposited on 27 Mar 2017
0 downloads since 12 months

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Date:January 2017
Deposited On:27 Mar 2017 06:33
Last Modified:09 Dec 2017 00:30
Publisher:World Scientific Publishing Co. Pte. Ltd.
ISSN:0129-0541
Publisher DOI:https://doi.org/10.1142/S0129054117500046
Related URLs:https://arxiv.org/abs/1202.4160
Other Identification Number:merlin-id:14700

Download