2025-01-01から1年間の記事一覧

Generating All the Minimal Separators of a Graph

問題 グラフ $G = (V, E)$ の頂点部分集合 $S \subseteq V$ が separator であるとは $G \setminus S$ が非連結となることをいう.包含関係の意味で極小の separator を minimal separator という.minimal separator を列挙せよ. 理論 Minimal separator …

代表元を変更できる Union Find

Union-Find データ構造では各頂点が自分の親を覚えて根を木の代表元に採用します.よくある実装では根の親ポインタは特に指すものがないので None にしたりグループのサイズを覚えたりしますが.ここに代表元を登録するようにすれば代表元を任意に選択できる…

ネットワーク単体法の実装

ネットワーク単体法 (network simplex algorithm) は最小費用流問題に対する実用的に高速なアルゴリズムです.この記事ではそれなりに高速なネットワーク単体法をフルスクラッチで実装するための技術を紹介します. ネットワーク単体法の概要 $G = (V, A)$ …