2013- Reprints: Operations Research and Decisions

Expand all

The uncapacitated swapping problem on a line and on a circle, Discrete Applied Mathematics, 161(4-5), 454-465, 2013.
S. Anily and A. Pfeffer
(Reprint No. 231)

 

>>

The uncapacitated swapping problem is defined by a graph consisting of n vertices, and m 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)-time algorithm for a line and an O(n3)-time algorithm for a circle.

 

Tel Aviv University makes every effort to respect copyright. If you own copyright to the content contained
here and / or the use of such content is in your opinion infringing, Contact us as soon as possible >>