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
