Premium
Polynomial time algorithm for constructing vertex‐disjoint paths in transposition graphs
Author(s) -
Fujita Satoshi
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20356
Subject(s) - combinatorics , vertex (graph theory) , mathematics , time complexity , disjoint sets , discrete mathematics , graph , algorithm
A transposition graph is a Cayley graph in which each vertex corresponds to a permutation and an edge is placed between permutations iff they differ by exactly one transposition. In this article, we propose an efficient 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 in the number of destination vertices, and the resultant path connecting s and each destination is longer than the distance to the destination by at most 16. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010