Permutation Routing via Matchings
Peter H yer, Kim Skak Larsen · 1996
The following routing problem on an undirected graph is considered: Initially, each node of the graph contains exactly one packet. Each node is the destination node of exactly one packet, so the initial state can be considered a permutation of the packets. The packets are routed to their destination nodes by a sequence of steps. In one step, each packet can either remain at its current location, or it can be swapped with a neighbor, i.e., a step is determined by a matching of the participating nodes. The time complexity of the previously best algorithm for routing all packets to their destination nodes given any initial permutation in a graph with n nodes was bounded by 13/5 n. We present an algorithm running in at most 2n-3 steps, where n<1, at the same time simplifying the analysis of the time complexity.