Computer Science – Data Structures and Algorithms
Scientific paper
2012-02-19
Computer Science
Data Structures and Algorithms
19 pages
Scientific paper
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., a routing function that only implies shortest paths can be realized in every circular-arc graph, where at most two (strict) intervals are stored at the ends of every edge. 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. Further, we show that the constructed 2-interval routing scheme can be represented as an 1-interval routing scheme with at most one additional interval assigned for each vertex of the graph and we outline an algorithm to implement the routing scheme for n-vertex circular-arc graphs in O(n^2) time.
Gurski Frank
Poullie Patrick Gwydion
No associations
LandOfFree
Interval Routing Schemes for Circular-Arc Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interval Routing Schemes for Circular-Arc Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval Routing Schemes for Circular-Arc Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-419509