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

点击翻译按钮获取中文摘要

本研究では、準最適化問題(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)時間で止まる。