A Time- and Communication-Optimal Distributed Sorting Algorithm in a Line Network and Its Extension to the Dynamic Sorting Problem(Algorithms and Data Structures)

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents a strictly time- and communication-optimal distributed sorting algorithm in a line network. A strictly time-optimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time- and communication-optimal. Moreover, an extension to the dynamic sorting problem is described.

• 社団法人電子情報通信学会の論文
• 2004-02-01

著者

• SASAKI Atsushi

  NTT Communication Science Laboratories, NTT Corporation

• Sasaki Atsushi

  Ntt Communication Science Laboratories Ntt Corporation

関連論文

• Formulation of Mobile Agent Allocation and Its Strong NP-Completeness(Complexity Theory)
• A Time- and Communication-Optimal Distributed Sorting Algorithm in a Line Network and Its Extension to the Dynamic Sorting Problem(Algorithms and Data Structures)
• 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)

スポンサーリンク