The uncapacitated swapping problem on a line and on a circle

The uncapacitated swapping problem   is defined by a graph consisting of nn vertices, and mm object types. Each vertex of the graph is associated with two object types: the one that it currently holds, and the one it demands. Each vertex holds or demands at most one unit of an object. The problem is balanced in the sense that for each object type, its total supply equals its total demand. A vehicle of unlimited capacity is assumed to transport the objects in order to fulfill the requirements of all vertices. The objective is to find a shortest route along which the vehicle can accomplish the rearrangement of the objects, given designated initial and terminal vertices. The uncapacitated swapping problem on a general graph, including a tree graph, is known to be NP-Hard  . In this paper we show that for the line and circle graphs, the problem is polynomially solvable: we propose an O(n)O(n)-time algorithm for a line and an O(n3)O(n3)-time algorithm for a circle.