Formulation of Mobile Agent Allocation and Its Strong NP-Completeness

Atsushi SASAKI  Tadashi ARARAGI  Shigeru MASUYAMA  Keizo MIYATA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.5   pp.1060-1063
Publication Date: 2005/05/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.5.1060
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Complexity Theory
strong NP-completeness,  mobile agents,  communication cost,  subgraph isomorphism,  load balancing,  

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

We formally define the mobile agent allocation problem from a system-wide viewpoint and then prove that it is strongly NP-complete even if each agent communicates only with two agents. This is the first formal definition for scheduling mobile agents from the viewpoint of load balancing, which enables us to discuss its properties on a rigorous basis. The problem is recognized as preemptive scheduling with independent tasks that require mutual communication. The result implies that almost all subproblems of mobile agent allocation, which require mutual communication of agents, are strongly NP-complete.