cad a22 4500 467973717 20181103044555.0 cr unu---uuuuu 170328e201701 xx s 000 0 eng 10.5167/uzh-136405 doi 10.1142/S0129054117500046 doi (ZORA)oai:www.zora.uzh.ch:136405 000 ddc Gurski Frank Interval routing schemes for circular-arc graphs [Elektronische Daten] [Frank Gurski, Patrick Poullie] restrictedAccess eu-repo 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 Department of Informatics zora Poullie Patrick joint author International Journal of Foundations of Computer Science 28(1):39-60 https://www.zora.uzh.ch/id/eprint/136405/1/ZORA136405.pdf text/html WWW-Backlink auf das Repository 1 Journal Article PeerReviewed zora ZORA 856 40 https://www.zora.uzh.ch/id/eprint/136405/1/ZORA136405.pdf text/html WWW-Backlink auf das Repository ZORA 100 1- Gurski Frank ZORA 700 1- Poullie Patrick joint author ZORA 773 0- International Journal of Foundations of Computer Science 28(1):39-60 BK010053 XK010053 XK010000 ZORA ZORA ZORA Journal Article restrictedAccess