New Routing Schemes for Interval, Circular-Arc, and Permutation Graphs

F.F. Dragan and I. Lomonosov (USA)


Communication algorithms, message routing, intersection graphs.


In this note we present new routing schemes for three classes of intersection graphs: interval graphs, circular-arc graphs and per mutation graphs. The routing schemes are compact, efficient and optimal for interval and circular-arc graphs and almost optimal for permutation graphs. For interval graphs, our routing scheme outperforms existing ones in efficiency. To the best of our knowl edge, these are first non-trivial routing schemes that are presented for circular-arc graphs and permutation graphs.

Important Links:

Go Back