概要 要素の集合を つに分割することを 回行って、どの 要素もどこかで分離されているようにすることができる。 向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。 向きの無い分割 問題例 無向グラフ があり、各辺には正の重み…

問題 文字集合を とする文字列 と がある。 の長さ の連続部分列のそれぞれについて、 にマッチするか判定せよ。 ただし文字列がマッチするとは、それぞれの文字列中の を好きな文字に置き換えたときに両文字列が一致することを指す。 解法 (Clifford & Clif…

概要 半順序集合の最大反鎖の計算は通常、Dilworth の定理を用いて最小パス被覆に帰着し、そこから更に二部マッチングへの帰着を行う。 本記事では (最終的にかなり近いアルゴリズムにはなるものの) 直接最小カットに帰着する手法を説明する。 また関連する…