사이클 상에서 정렬을 위한 로봇의 최소 움직임 = Minimum Movement of a Robot for Sorting on a Cycle

다국어 초록 (Multilingual Abstract)

In a graph G=(V, E) with n vertices, there is an unique box which is finally laid on each vertex. Thus each vertex and box is both numbered from 1 to n and the box i should be laid on the vertex i. But, the box ${\pi}$(i) is initially located on the vertex i according to a permutation ${\pi}$. In each step, the robot can walk along an edge of G and can carry at most one box at a time. Also when arriving at a vertex, the robot can swap the box placed there with the box it is carrying. The problem is to minimize the total step so that every vertex has its own box, that is, the shuffled boxes are sorted. In this paper, we shall find an upper bound of the minimum number of steps and show that the movement of the robot is found in $O(n^2)$ time when G is a cycle.

참고문헌 (Reference)

1 E. Dalhaus, "The train marshalling problem" 103 (103): 41-54, 2000

2 M. R. Jerrum, "The complexity of finding minimum-length generator sequence" 36 (36): 265-289, 1985

3 L. Manivel, "The Symmetric Functions, Schubert Polynomials and Degeneracy Loci" American Mathematical Society 2001

4 D. E. Knuth, "The Art of Computer Programming, vol. 3" Addison-Wesley 1998

5 K. Yamanaka, "Swapping labeled tokens on graphs" 586 (586): 81-94, 2015

6 C. Busing, "Robust Algorithms for Sorting Railway Cars" 350-361, 2010

7 A. Cayley, "Note on the theory of permutations" Taylor&Francis Group 2009

8 R. Jacob, "Multistage methods for freight train classification" 57 (57): 87-105, 2011

9 D. Graf, "How to sort by walking on a tree" 643-655, 2015

10 K. Yamanaka, "Efficient enumeration of all ladder lotteries and its application" 411 (411): 1714-1722, 2010