A Linear-Time Algorithm for Determining the Order of Moving Products in Realloction Problems

Hiroyoshi MIWA  Hiro ITO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.3   pp.534-543
Publication Date: 1997/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
graph,  reallocation,  linear-time,  NP-complete,  

Full Text: PDF(817KB)>>
Buy this Article




Summary: 
The reallocation problem is defined as determining whether products can be moved from their current storehouses to their target storehouses in a number of moves that is less than or equal to a given number. This problem is defined simply and has many practical applications. We previously presented necessary and sufficient conditions whether an instance of the reallocation problem is feasible, as well as a linear-time algorithm that determines whether aall products can be moved, when the volume of the products is restricted to one. However, a linear-time algorithm that generates the order of moving the products has not been reported yet. Such an algorithm is proposed in this paper. We have also previously proved that the reallocation problem is NP-complete in the strong sense when the volume of the products is not restricted and the products have evacuation storehouses show that the reallocation problem is NP-complete in the strong sense even when none of the products has evacuation storehouses.