サブロウ丸

主にプログラミングと数学

グラフ理論

Preflow Push-Relabel アルゴリズム 改良

Qiitaに記事を投稿しました。 qiita.com 概要 preflow-push algorithm はネットワーク G=(V, E)上の最大フローを求めるアルゴリズムです. (中略) この記事では, 計算量を削減する改良として, FIFO Preflow-Push AlgorithmとHighest-Label Preflow-Push Algor…

Subgraph isomorphism (J. R. ULLMANNのアルゴリズム)

Qiitaに記事を投稿しました。 グラフ の中に が部分グラフとして存在するかどうかを判断する問題です. Subgraph isomorphismの解法として, J. R. ULLMANNのアルゴリズム [1] を紹介します. 参考文献 [1] ULLMANN, Julian R. An algorithm for subgraph isomo…

Eppstein's Algorithm (Find the K shortest paths) 解説と実装 (Python)

Qiitaに記事を投稿しました。 K Shortest Path Problem (KSP) とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です。 多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法として Eppsteinの アルゴリズムを実装し…

雰囲気で理解する Yen's algorithm (Find the K shortest paths)

Qiitaに記事を投稿しました。 K Shortest Path Problem とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です. 色々バリエーションがあるみたいですが, 今回は多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法…

フロー分解

次のようなネットワークのフロー分解を考えます。 まず、フローとは何かという話ですが、 始点(図s)から終点に(図t)に水を流すことを考えます。 そのときの"水の流れ"のことをフローと呼びますが、それにはいくつか条件があります。 図のノード(丸)とノード…