luzhiled1333 / comp-library

Creative Commons Zero v1.0 Universal

4 stars 2 forks source link

[graph/flow] 一般グラフの最大マッチング #165

Open ei1333 opened 1 year ago

ei1333 commented 1 year ago

Un-weighted

$O(|V|^3)$ $O(|V||E| \log |V|)$ $O(|E| \sqrt {|V|})$

Description

File Name

src/*

TODO

[ ] 実装
[ ] ドキュメント作成
[ ] unit-test
[ ] verify

note

reference material
- (url)
implementation
- (url)
関連 issue / PR
- #
verify:
- (url)

Weighted

Description

$O(|V|^3)$

File Name

src/*

TODO

[ ] 実装
[ ] ドキュメント作成
[ ] unit-test
[ ] verify

note

reference material
- (url)
implementation
- (url)
関連 issue / PR
- #
verify:
- https://judge.yosupo.jp/problem/general_weighted_matching

ei1333 commented 1 year ago

密グラフ・疎グラフのためのアルゴリズムをどうするか議論が必要な気がしている（例えば、Dijkstraの $O(E \log V)$ と $O(V^2)$）