Line topology [1]}, [2]}, [3]}, [4]} is one of the simplest interconnection network topologies, where each agent is connected to exactly two neighboring agents other than the two end agents that are connected to only one neighboring agent (see Fig. REF ). We assume that each agent in a task swapping graph of line topology is labeled in ascending order from left to right as shown in Fig. REF . A task swapping graph of line topology having \(n\)  agents with their task assignment represented by permutation \(p \in \mathfrak {S}_n\)  is denoted as \(\Gamma _p^{L(n)}\) . For example, a task swapping graph of Fig. REF (a) is denoted as \(\Gamma _{p_1}^{L(8)}\)  and a task swapping graph of Fig. REF (b) is denoted as \(\Gamma _{p_2}^{L(8)}\) , respectively, where \(p_1=2\,5\,6\,3\,1\,4\,8\,7 \in \mathfrak {S}_8\)  and \(p_2=1\,6\,2\,3\,4\,5\,7\,8 \in \mathfrak {S}_8\) . Recall that a right multiplication of permutation \(p\)  by transposition \((i\,i+1)\)  exchanges the values in position \(i\)  and position \(i+1\)  of \(p\) . Since only adjacent task swappings are allowed, we use the generating set \(S_1=\lbrace (i\,i+1) : 1 \le i < n\rbrace \)  to find a minimum-length sequence of adjacent task swappings needed from \(\Gamma _{\pi _1}^{L(n)}\)  for \(\pi _1 \in \mathfrak {S}_n\)  to reach \(\Gamma _{\pi _2}^{L(n)}\)  for \(\pi _2 \in \mathfrak {S}_n\) . For example, the number of the minimum adjacent task swappings needed from \(\Gamma _{p_1}^{L(8)}\)  in Fig. REF (a) to reach \(\Gamma _{p_2}^{L(8)}\)  in Fig. REF (b) is the minimum length of a permutation factorization of \({p_1}^{-1}p_2\)  using the generating set \(S_1^\prime =\lbrace (i\,i+1) : 1 \le i < 8\rbrace \) . Observe that \({p_1}^{-1}p_2\)  takes \(p_1\)  to \(p_2\) , i.e., \(p_1({p_1}^{-1}p_2)=(p_1{p_1}^{-1})p_2=p_2\) . Equivalently, it is viewed as taking \(p_2^{-1}p_1\)  to the identity permutation \(I\) , i.e., \(p_2^{-1}p_1({p_1}^{-1}p_2)=I\) . Thus, a minimum-length permutation factorization of \({p_1}^{-1}p_2\)  using the generating set \(S_1^\prime \)  corresponds to a shortest path from vertex \(p_2^{-1}p_1\)  to vertex \(I\)  in the bubble sort Cayley graph \(\text{BS}_8\) . Thus, it is reduced to find a shortest path from
\(p_2^{-1}p_1=3\,6\,2\,4\,1\,5\,8\,7\)  to permutation \(I\)  in the bubble sort Cayley graph \(\text{BS}_8\) :
\(3\,6\,2\,4\,1\,5\,8\,7 \xrightarrow{} 3\,2\,6\,4\,1\,5\,8\,7\)\( \xrightarrow{} 3\,2\,4\,6\,1\,5\,8\,7 \xrightarrow{} 3\,2\,4\,1\,6\,5\,8\,7 \)\(\xrightarrow{} 3\,2\,4\,1\,5\,6\,8\,7 \xrightarrow{} 3\,2\,4\,1\,5\,6\,7\,8 \)\(\xrightarrow{} 2\,3\,4\,1\,5\,6\,7\,8 \xrightarrow{} 2\,3\,1\,4\,5\,6\,7\,8 \)\(\xrightarrow{} 2\,1\,3\,4\,5\,6\,7\,8 \xrightarrow{} 1\,2\,3\,4\,5\,6\,7\,8\) , where the label of each arrow denotes an edge in \(\text{BS}_8\) . Therefore, \({p_1}^{-1}p_2={(p_2^{-1}p_1)}^{-1}=(2\,3)(3\,4)(4\,5)(5\,6)(7\,8)(1\,2)(3\,4)(2\,3)(1\,2)\) . It follows that the resulting minimum-length sequence of adjacent task swappings needed from \(\Gamma _{p_1}^{L(8)}\)  to reach \(\Gamma _{p_2}^{L(8)}\)  is \(((2\,3)\) , \((3\,4)\) , \((4\,5)\) , \((5\,6)\) , \((7\,8)\) , \((1\,2)\) , \((3\,4)\) , \((2\,3)\) , \((1\,2))\) . It is interpreted as a sequence of task swappings so that a task swapping between agents in the first term (agent 2 and agent 3) is followed by a task swapping between agents in the second term (agent 3 and agent 4), and so on, until arriving at a task swapping between agents in the last term (agent 1 and agent 2) of the sequence. We see that the length of the sequence is 9, implying that at least 9 adjacent task swappings are needed from \(\Gamma _{p_1}^{L(8)}\)  to reach \(\Gamma _{p_2}^{L(8)}\) . Algorithm  describes the procedure of converting \(\Gamma _{\pi _1}^{L(n)}\)  into \(\Gamma _{\pi _2}^{L(n)}\)  by using a minimum-length sequence of adjacent task swappings. It is known from group theory that the minimum length of permutation \(p \in \mathfrak {S}_n\)  using the generating set \(S_1\)  is the inversion number [5]}, [6]} of \(p\) , where the inversion number of \(p\)  is defined as \(|\lbrace (i, j): i < j, p(i) > p(j)\rbrace |\) . The maximum inversion number of permutations of \(n\)  elements is \(n(n-1)/2\) , which corresponds to permutation \(n\,n-1\,\cdots \,2\,1\)  [5]}. Now, the minimum number of adjacent task swappings needed from \(\Gamma _{\pi _1}^{L(n)}\)  for \(\pi _1 \in \mathfrak {S}_n\)  to reach \(\Gamma _{\pi _2}^{L(n)}\)  for \(\pi _2 \in \mathfrak {S}_n\)  is the inversion number of \({\pi _1}^{-1}\pi _2\)  (or \({\pi _2}^{-1}\pi _1)\) . It follows that the least upper bound of the minimum number of adjacent task swappings needed from \(\Gamma _{\pi _1}^{L(n)}\)  to reach \(\Gamma _{\pi _2}^{L(n)}\)  is \(n(n-1)/2\) , which is the maximum inversion number of permutations of \(n\)  elements. We also see that it coincides the diameter of bubble sort Cayley graph \(\text{BS}_n\) .
