計算問題の並列化可能性と並列化不能性

计算问题的并行性和非并行性

• 批准号: 06780252
• 负责人: 陳 致中
• 金额: $ 0.26万
• 依托单位: Tokyo Denki University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780252/
• 关键词: 準最適化問題; 並列化可能性; 並列化不能性; 並列RAM; 対数多項式時間; 並列アルゴリズム

本研究では、準最適化問題(optimality problem)の並列化可能性と並列化不能性に焦点を当てた。準最適化問題は、最適化問題(optimization problem)の自然な近似となるので、盛んに研究されてきた。ほとんどすべての自然な準最適化問題が逐次的に効率よく解けるのに対し、ごく少数の準最適化問題の並列化可能性が証明されたのみである。実際、多くの自然な準最適化問題の並列化可能性がまだ証明されていない。そこで、本研究では、次の二つの自然な準最適化問題に焦点を当て、新しいアイディアを導入することによって、その並列化可能性を証明した。問題1:入力として無向平面グラフG=(V,E)が与えられたとき、次の条件(1)と(2)を満たすようなU⊆Vを求めよ:(1)Uによって導出される部分グラフが閉路(cycle)を持たない。(2)任意のu∈V-Uに対して、U∪{u}によって導出される部分グラフが閉路を持つ。結果1:問題1を解く並列アルゴリズムを設計した。このアルゴリズムは並列RAM上でO(n)個のブロセッサを用いてO(log^3n)時間で止まる。問題2:入力として無向平面グラフG=(V,E)と関数f:V→Nが与えられたとき、次の条件(1)と(2)を満たすようなU⊆Vを求めよ:(1)Uによって導出される部分グラフにおいて、次数がf(v)を越える頂点vが存在しない。(2)任意のv∈V-Uに対して、U∪{v}によって導出される部分グラフにおいて、次数がf(v)を越える頂点vが存在する。結果2:問題2を解く並列アルゴリズムを設計した。このアルゴリズムは並列RAM上でO(n)個のブロセッサを用いてO(log^5n)時間で止まる。

In this paper, we focus on the parallelism possibility and parallelism impossibility of quasi-optimization problems. Quasi-optimization problems are natural approximations of optimization problems. For natural quasi-optimization problems, the probability of parallelization is proved. The parallelization possibility of real and multi-natural quasi-optimization problems is proved. In this paper, we prove the possibility of parallel optimization of natural optimization problems. Problem 1: The force into the undirected plane G=(V,E) and the second condition (1) and (2) are determined by:(1)U is derived from the partial loop (cycle). (2)Any u∈V-U Result 1: Problem 1 is solved in parallel. O(log^3n) time is required for O(n) pieces of parallel RAM. Problem 2: The force into the plane G=(V,E) f:V→N and the condition (1) f (2) f (2) f(3) f (4) f (5) f (5) f (6) f (7) f (8) f (9) f (9) f(9) (2)Any v∈V-U, U ∈ {v}, U ∈ {v}. Result 2: Problem 2 is solved by parallel design. O(log^5n) time is required for O(n) pieces of parallel RAM.

项目成果

陳 致中: "The Maximal f-Dependent Set Problem for Planar Graphs Is in NC," Thcoretical Computer Science. (掲載受理済み).

Chizhong Chen：“平面图的最大 f 相关集问题在 NC 中”，Thcoretical Computer Science（已接受出版）。

陳 致中: "Parallel Algorithms for Maximal Acylic Sets," Proccedings of Aizu International Symposium on Parallel Algorithm/Architecture Synthesis. (掲載受理済み).

陈赤中：“最大无环集的并行算法”，会津国际并行算法/架构综合研讨会论文集（已接受出版）。