AbstractThe problem of routing permutations on graphs via matchings is considered, and we present a general algorithm which can be parameterized by different heuristics. This leads to a framework which makes the analysis simple and local.
Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: permutation routing, matching, graph algorithm
Selected references
- N. Alon, F. R. K. Chung, and R. L. Graham. Routing permutations on graphs via matchings (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 583-591, San Diego, California, 16-18 May 1993.
- Alan Roberts, Antonios Symvonis, and Louxin Zhang. Routing on trees via matchings. In Selim G. Akl and Frank K. H. A. Dehne and Jörg-Rüdiger Sack and Nicola Santoro, editors, Algorithms and Data Structures, 4th International Workshop, volume 955 of Lecture Notes in Computer Science, pages 251-262, Kingston, Ontario, Canada, 16-18 August 1995. Springer.
- Louxin Zhang. Optimal bounds for matching routing on trees. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 445-453, New Orleans, Louisiana, 5-7 January 1997.