論文賞 1994年度

[論文]

グラフを fg 辺彩色する近似アルゴリズム (日本応用数理学会論文誌 Vol.1,No.3,1991,pp.195-211)

[著者]

中野 真一(東北大学工学部情報工学科), 西関 隆夫(東北大学工学部情報工学科)

[受賞理由]

本論文は,並列処理のスケジュール問題に端を発する新しいタイプのグラフ彩色問題に対して,彩色に必要な最小色数の一つの簡明な上界を与え,その上界を実現する効率の良い彩色アルゴリズムを与えている. 平行辺をもつグラフGに対して,各頂点に接続する辺のうち同じ色をもつものの最大数が指定される従来の彩色問題を一般化し,2頂点をつなぐ辺のうち同じ色をもつものの最大数も指定されたときの彩色問題を考察している. このグラフ彩色問題の最小色数の一つの自明な下界に対して,その1.5倍が上界であることを深い理論展開に基づいて証明している. 実用から遊離しないところで新しい問題を開拓し定式化したこと,および,精密な理論展開によって一つの上界とそれを達成するアルゴリズムを与えたことの両面を総合して受賞に値すると評価された.

[論文]

Cahn-Hilliard方程式の差分法による数値的解析 (日本応用数理学会論文誌 Vol.3,No.3,1993,pp.217-228)

[著者]

降旗 大介(東京大学工学部物理工学科), 恩田 智彦(花王文理科学研究所),森 正武(東京大学工学部物理工学科)

[受賞理由]

本論文は,非線形偏微分方程式の一つであるCahn-Hilliard方程式に対する差分法による安定な数値解法を提案したものである. 差分法を適用するにあたっての課題は,安定な数値計算を保証する空間刻み幅と時間刻み幅の設定法である. 本論文では,これらの二つの刻み幅が満たすことが望ましい条件を表わすF-安定という新しい概念を提案し,これが安定な近似解を得るための基準となることを数値実験を通して示している. F-安定であればいつも不安定性がおさえられるという理論的保証が与えられているわけではないが,このような新しく画期的な概念を提唱したこと,その有効性が大きいと思われること,およびこの概念が新しい数学的な問題提起となっていることなどを総合して,受賞に値すると評価された.

[論文]

Durand-Kerner法の効率的な初期値の簡単な設定法 (日本応用数理学会論文誌 Vol.3,No.4,1993,pp.451-464)

[著者]

小澤 一文(東北大学情報処理教育センター)

[受賞理由]

本論文は,代数方程式のすべての解を同時に求めることができるDurand-Kerner法の初期値の新しく効率的な設定法を提案したものである. 初期値を,すべての解を含む円の周上にとることが必ずしも最良ではないことは以前から指摘されていたが,本論文では,解の重心とおのおのの解との距離の幾何平均を半径とする円の周上に初期値をとる方法が良いと主張し,それをいくつかの数値実験を通して確かめている. 本提案が簡明ですぐにでも試してみたくなるアイデアであるとの評価が,特に実務に近い立場から高く,ノート部門の受賞対象にふさわしいと判断された.