文献

J-GLOBAL ID：201602225416403691   整理番号：16A1323975

経路問題と離散数学-重みのあるグラフとないグラフ-

著者 (1件)： 小田芳彰 (慶応大 理工)
資料名： オペレーションズ・リサーチ
巻： 61  号： 12  ページ： 837-843  発行年： 2016年12月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,最短路問題に代表される経路問題とその背景にある基本的な問題,性質について紹介する。経路問題においては各2都市間の距離が重要な要素になり,各辺に重みと呼ばれる実数値を割り当てた重み付きグラフが対象になるが,重みのないグラフでの性質を利用することで,見通しがよくなることが多く,本稿ではこのような部分に目を向けていく。(著者抄録)

シソーラス用語： *最短路問題 ,  *問題 ,  巡回セールスマン問題 ,  探索理論 ,  マッチング ,  ネットワーク ,  *Hamilton閉路 ,  幅優先探索 ,  重み付きネットワーク ,  理論
準シソーラス用語： 最短経路問題 ,  中国郵便配達人問題

分類 (1件)： ネットワーク法  (KA03040X)

引用文献 (12件)：

• P. E. Hart, N. J. Nilsson and B. Raphael, “A formal basis for the heuristic determination of minimal cost paths,“ IEEE Transactions on Systems Science and Cybernetics, 4, pp. 100-107, 1968.
• R. W. Floyd, “Algorithm 97: Shortest path,“ Communications of the ACM, 5, p. 345, 1962.
• S. Warshall, “A theorem on Boolean matrices,“ Journal of the ACM, 9, pp. 11-12, 1962.
• J. Edmonds, “Paths, trees, and flowers,“ Canadian Journal of Mathematics, 17, pp. 449-467, 1965.
• B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 5th edition, Springer, 2012.

タイトルに関連する用語 (3件)： 経路問題 ,  離散数学 ,  グラフ