文献

J-GLOBAL ID：201202252382823407   整理番号：12A0924173

離散凸解析から見たDijkstra法

Dijkstra Algorithm Viewed from Discrete Convex Analysis

著者 (2件)： MUROTA Kazuo (Univ. Tokyo, Tokyo, JPN) ,  SHIOURA Akiyoshi (Tohoku Univ., Sendai, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 24(COMP2012 8-11)  ページ： 39-43  発行年： 2012年05月07日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： ダイクストラ法は,非負の枝長をもつ有向グラフにおける単一始点最短路問題に対する有名なアルゴリズムである。本稿では,ダイクストラ法を離散凸解析の視点から調査し,ダイクストラ法が,L凹関数最大化に対する最急上昇法を実装したものと見なせることを指摘する。(著者抄録)

シソーラス用語： 最短路問題 ,  *アルゴリズム ,  離散系 ,  傾斜法 ,  機能 ,  操作 ,  凸形
準シソーラス用語： *ダイクストラ法 ,  最大化 ,  上昇法

分類 (2件)： グラフ理論基礎  (IA02020S) ,  数理計画法  (KA03030M)

引用文献 (9件)：

• AHUJA, R. K. Network Flows : Theory, Algorithms, and Applications. 1993
• DIJKSTRA, E. W. A note on two problems in connexion with graphs. Numerische Mathematik. 1959, 1, 269-271
• IWATA, S. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. Journal of the ACM. 2001, 48, 761-777
• KOLMOGOROV, V. New algorithms for convex cost tension problem with application to computer vision. Discrete Optimization. 2009, 6, 378-393
• MUROTA, K. Discrete convex analysis. Mathematical Programming. 1998, 83, 313-371

タイトルに関連する用語 (1件)： 凸解析