最大フロー問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/24 20:29 UTC 版)
最大フロー問題（さいだいフローもんだい、英: Maximum flow problem）または最大流問題とは、単一の始点から単一の終点へのフローネットワークで最大となるフローを求める問題である[1]。単にフローの最大値を求める問題と定義されることもある。最大フロー問題は、より複雑なネットワークフロー問題である最小費用流問題の特殊ケースと見ることもできる。
| |||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||
- ^ a b T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン 『アルゴリズムイントロダクション』 近代科学社、2013年12月17日（原著2009年7月31日）、第3版（日本語）。ISBN 476490408X。
- ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. (1978年). “An O(”. Information Processing Letters 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9. ISSN 00200190.
- ^ Daniel Dominic Kaplan Sleator. An o(nm log n) algorithm for maximum network flow.
- ^ a b c Goldberg, A V; Tarjan, R E (1986年). A new approach to the maximum flow problem. pp. 136–146. doi:10.1145/12130.12144.
- ^ King, V.; Rao, S.; Tarjan, R. (1994年). “A Faster Deterministic Maximum Flow Algorithm”. Journal of Algorithms 17 (3): 447–474. doi:10.1006/jagm.1994.1044. ISSN 01966774.
- ^ Goldberg, Andrew V.; Rao, Satish (1998年). “Beyond the flow decomposition barrier”. Journal of the ACM 45 (5): 783–797. doi:10.1145/290179.290181. ISSN 00045411.
- ^ Orlin, James B. (2013年). Max flows in O(nm) time, or better. pp. 765. doi:10.1145/2488608.2488705.
[続きの解説]
「最大フロー問題」の続きの解説一覧
- 1 最大フロー問題とは
- 2 最大フロー問題の概要
- 3 参考文献
- 最大フロー問題のページへのリンク
