Vertex-Disjoint Paths in Transposition Graphs

S. Fujita (Japan)

Keywords

Transposition graph, routing, vertexdisjoint, matching.

Abstract

A transposition graph is a Cayley graph in which vertices correspond to permutations and edges are placed between permutations that differ by exactly one transposition. In this paper, we propose an algorithm to find a collection of vertex-disjoint paths connecting a given source vertex s and a given set of destination vertices D. The running time of the algorithm is polynomial to the number of des tination vertices, and the resultant path connecting s and each destination is longer than the length of a shortest path connecting those vertices by at most fourteen.

Important Links:



Go Back