Formulation of Mobile Agent Allocation and Its Strong NP-Completeness(Complexity Theory)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2005-05-01
著者
-
Masuyama Shigeru
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
Miyata Keizo
Department Of Knowledge-based Infomation Engineering Toyohashi University Of Technology
-
Masuyama Shigeru
Toyohashi Univ. Technol. Toyohashi‐shi Jpn
-
Araragi Tadashi
NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation
-
SASAKI Atsushi
NTT Communication Science Laboratories, NTT Corporation
-
Araragi Tadashi
Ntt Communication Science Laboratories Nippon Telegraph And Telephone Corporation
-
Araragi Tadashi
Ntt Communication Science Laboratories Ntt Corporation
-
Sasaki Atsushi
Ntt Communication Science Laboratories Ntt Corporation
関連論文
- A New Aspect of the Carotid Body Function Controlling Hypoxic Ventilatory Decline in Humans
- An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
- An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph
- Cause Information Extraction from Financial Articles Concerning Business Performance
- Control of Upper Airway Function in Response to Hypoxia in Patients with Obstructive Sleep Apnea Syndrome
- Compensatory Excretion of Prostacyclin and Thromboxane Metabolites in Obstructive Sleep Apnea Syndrome
- The Effect of Changing Rate of PIO_2 Fall on Relationship between Ventilatory and Heart Rate Response to Progressive Hypoxia
- Analysis of Heart Rate Profile during Obstructive Sleep Apnea
- Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
- Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph K_n
- PROPASAL OF THE UNRESTRICTED LR(k) GRAMMAR AND ITS PARSER
- Checking Liveness Properties of Concurrent Systems by Using Reinforcement Learning
- A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs(Invited Papers from New Horizons in Computing)
- An Informative DOM Subtree Identification Method from Web Pages in Unfamiliar Web Sites
- Formulation of Mobile Agent Allocation and Its Strong NP-Completeness(Complexity Theory)
- Reasoning about Mental State Compatibilities of Rational Agents and Its Applications( Software Agent and Its Applications)
- Multiple Document Summarization System GOLD(Special Issue on Text Processing for Information Access)
- UGLR Parser for Phrase Structure Languages as an Extension of GLR Parser (Special Section on Discrete Mathematics and Its Applications)
- T1 MINIMUM VERTEX RANKING SPANNING TREE PROBLEM : A TUTORIAL(Tutorial speech)
- A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
- A Statistical Method for Acquiring Knowledge about the Abbreviation Possibility of Some of Multiple Adnominal Phrases(Special Issue on Text Processing for Information Access)
- A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs
- An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
- An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method (Special Section on Discrete Mathematics and Its Applications)
- Minimum Vertex Ranking Spanning Tree Problem(TUTORIAL SPEECH)
- On the Ambiguity Reduction Ability of a Probabilistic Context-Free Grammar(Special Section on Discrete Mathematics and Its Applications)
- MINIMUM DELAY SEMIJOIN SCHEDULES FOR LOCAL AREA DISTRIBUTED DATABASE SYSTEMS(Mathematical Theories on Computing Schemes and Their Applications)
- Assigning Polarity to Causal Information in Financial Articles on Business Performance of Companies
- An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
- On the Largest Common Subgraph Problem
- A Time- and Communication-Optimal Distributed Sorting Algorithm in a Line Network and Its Extension to the Dynamic Sorting Problem(Algorithms and Data Structures)
- An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
- Extraction of Effect and Technology Terms from a Patent Document(Theory and Methodology)
- A Distributed Task Assignment Algorithm with the FCFS Policy in a Logical Ring(Algorithms and Data Structures)
- A Time-Optimal Distributed Arrangement Selection Algorithm in a Line Network (Special Issue on Selected Papers from LA Symposium)
- Extraction of Effect and Technology Terms from a Patent Document
- Automatic Construction of Train Arrival and Departure Schedules at Terminal Stations
- Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
- A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs
- A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance
- 4A3 AN ONLINE SCHEDULING ALGORITHM THAT MINIMIZES THE TOTAL COMPLETION TIME IN AN AGV SYSTEM AND ITS COMPETITIVE ANALYSIS(Technical session 4A: Material handling system)
- 5A2 AUTOMATIC CONSTRUCTION OF TRAIN ARRIVAL AND DEPARTURE SCHEDULES IN TERMINAL STATIONS(Technical session 5A: OS4: Railway scheduling)