• 検索結果がありません。

研究会推薦博士論文速報 : Studies on Quickest Flow Problems in Dynamic Networks and Arborescence Problems in Directed Graphs - A Theoretical Approach to Evacuation Planning in Urban Areas

N/A
N/A
Protected

Academic year: 2021

シェア "研究会推薦博士論文速報 : Studies on Quickest Flow Problems in Dynamic Networks and Arborescence Problems in Directed Graphs - A Theoretical Approach to Evacuation Planning in Urban Areas"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)連載 ─ 研究会推薦博士論文速報 ─ 学位論文題目 Studies on Quickest Flow Problems in Dynamic Networks and Arborescence Problems in Directed Graphs - A Theoretical Approach to Evacuation Planning in Urban Areas(邦訳:動的ネッ トワーク上の最速フロー問題と有向グラフ上の有向木問題の研究─都市における避難計画に対す る理論的アプローチ)   大学 京都大学       取得年月 2009 年 3 月  学位種別 博士(工学) 氏 名 神山 直之(中央大学理工学部情報工学科 助教) 推薦研究会 アルゴリズム 推薦文 本論文の有向木詰め込みに関する最大最小定理は,Edmonds による離散数学の重要な定理の一般 化であり,基礎理論に新たな展開をもたらす結果として国際的評価も高い.同時に,定理が「災 害時の避難計画」という現実問題の研究から導かれたことは,実用性の高さを窺わせ,他の現実 問題への今後の応用も期待される.  近年多発する地震や津波などを背景に,これらの大規模災. さらに,理論的に. 害に対する危機管理システムの構築の必要性が声高に叫ばれ. もグラフ理論・離. ている.しかし,これまでこのような危機管理システムの構築. 散最適化の分野で. は,長年の経験や勘に頼るところが大きかった.本論文は,そ. は非常に古典的か. のような危機管理システム構築のための理論的基礎研究を,離. つ重要な問題の 1. 散最適化の枠組みで行うことを目的としている.本論文は大. つである.具体的. きく分けて 2 つの問題を扱っている.1 つは,最適な避難計画. には,入力として. を求める動的ネットワーク上の最速フロー問題であり,もう 1. 有向グラフが与え. つは都市の道路ネットワークの頑健性の計算や避難経路の作. られ,ある 1 つの. 成をモデル化している有向グラフ上の有向木問題である.. 点が根として指定.  動的ネットワークとは,基礎となる有向グラフの各辺に移. されたとき,可能な限り辺素な有向木を詰め込む問題である.. 動時間と容量,そして各点にはサプライが与えられたネットワ. 有向木とは閉路を持たない部分グラフであり,すべての辺が根. ークである.このとき,最速フロー問題の目的はすべてのサプ. から遠ざかる方向に向き付けられているものである.この問題. ライを目的地であるソースまで可能な限り短い時間で流すこ. に対しては 1973 年に Jack Edmonds によって詰め込むことので. とである.この問題に対しては,2000 年に Hoppe と Tardos に. きる全域的な有向木の数と根を含むカットの大きさに関する. よって多項式時間アルゴリズムが与えられているが,このアル. 最大最小定理が証明された.この定理は Ford と Fulkerson によ. ゴリズムは繰り返し劣モジュラ関数最小化問題を解く必要が. って与えられた最大流最小カット定理と並ぶ,離散最適化の. あり実用的であるとは言えない.よって実用的なネットワー. 分野においては非常に重要な定理である.この定理が証明さ. クの構造に対して高速かつ簡便なアルゴリズムを開発する必. れた後,有向木の詰め込みに関しては活発に研究されさまざま. 要がある.この問題に対して本論文では京都のような碁盤の. な結果が得られてきたが,この定理自体の真の拡張は与えられ. 目状のネットワークを一般化したネットワークに対して高速. ておらず,真に拡張することは難しいのではと予想されていた.. なアルゴリズムを開発した.このアルゴリズムは時間拡大ネッ. しかし本論文ではこの予想に反し,この Edmonds の定理に対. トワークという,元のネットワークを時間ごとに拡大したもの. して根が単数であった条件を複数に,有向木が全域的であ. を用いている.この時間拡大ネットワーク自体は古くから知. った条件を根からの到達可能性にと拡張することに成功した.. られているものであるが,多項式時間アルゴリズムの開発には. この成果は有向木の研究に非常なインパクトを与え,Fujishige. 使えないと考えられていた,しかし,本論文では時間拡大ネッ. によるグラフ上の凸性といった新たな概念などが生まれる新し. トワークを縮小するというアイディアを導入し効率的なアルゴ. いきっかけとなった.また,この有向木の詰め込みに関係する. リズムの開発に成功した.さらに工学的な立場からは,フロー. 問題である独立有向木問題などに対しても,これまでの結果の. をただ早く流すだけではなく,交差点における混雑や使用する. 拡張などを導くことに成功した.. パスの種類などを考慮する必要がある.本論文ではこのような. (平成 22 年 3 月 31 日受付). 問題を扱うことのできる数理モデルを作成し,計算複雑性や多 項式時間で解けるクラス等を明らかにしている.  もう 1 つの有向グラフ上の有向木問題は,応用性が高いうえ 情報処理 Vol.51 No.11 Nov. 2010. 1499.

(2)

参照

関連したドキュメント

(Approximately 4,000 characters in Japanese, or 1,500 words in English. The Doctoral Thesis title, however, must be written in both Japanese and English.).. 博士論文審査委員会

Horikoshi Characteristics of multivalent impurity doped C60 films grown by MBE 14th International Conference on Molecular Beam Epitaxy, Tokyo, Japan, September 3-8, 2006..

Cioffi, “Pilot tone selection for channel estimation in a mobile OFDM systems,” IEEE Trans.. Sunaga, “Rayleigh fading compensation for QAM in land mobile ra- dio communications,”

1)研究の背景、研究目的

STUDIES ON FUNDAMENTAL PROBLEMS IN SEISMIC DESIGN ANALYSES OF CRITICAL STRUCTURES AND FACILITIES(.

Papers dis- cussing dynamical properties, statistical and mathematical results, stability investigation of the phase space structure, the phenomenon of Fermi acceleration,

In particular, we show that, when such a polynomial exists, it is unique and it is the sum of certain Chebyshev polynomials of the first kind in any faithful irreducible character of

In this section we apply approximate solutions to obtain existence results for weak solutions of the initial-boundary value problem for Navier-Stokes- type