For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Formulation of Mobile Agent Allocation and Its Strong NP-Completeness
Atsushi SASAKI Tadashi ARARAGI Shigeru MASUYAMA Keizo MIYATA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/05/01
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)>>
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.