New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Sparsity matroid （疎性マトロイド） #292

Open

hitonanode opened this issue May 3, 2023 · 2 comments

Labels

Owner

hitonanode commented May 3, 2023 •

edited

$(k, l) -$ 疎性マトロイド（無向グラフの辺集合 $E$ の独立性の定義：任意の $\emptyset \neq F \subset E$ について $|F| \le k |V(F)| - l$ が成立）は以下の一般化になっている：

グラフマトロイド
Bicircular matroid Bicircular matroid - Wikipedia
剛性マトロイド Rigidity matroid - Wikipedia

https://www.kurims.kyoto-u.ac.jp/coss/coss2011/tanigawa-2.pdf
https://qoj.ac/problem/6382

hitonanode added the enhancement label

Owner Author

hitonanode commented May 3, 2023

Pebble Game Algorithms and (k, l)-Sparse Graphs に載っていそう

Matroid oracle - Wikipedia の実装について

頂点側を $k$ 倍に拡張して辺側と 2 部マッチングする

Circuit-find oracle
- あらかじめ独立集合 $F \subseteq E$ がセットされる
  - DM 分解しておく
- $F + x$ に対する circuit-find oracle
  - $x$ の両端点に対応する頂点に $l + 1$ 個の空きが確保できるか確認する
  - Circuit がない -> DM 分解しておけば $O(1)$ ？
  - Circuit がある -> 線形時間？
独立性オラクル
- circuit-find oracle を $| F |$ 回使う？

Owner Author

hitonanode commented May 3, 2023 •

edited

Pebble Game Algorithms and (k, l)-Sparse Graphs

本質的には最大二部マッチングを交互道でやっているやつと同じに見えるが、定数倍が軽く一般化も楽に見えるので実装方針はこれがよさそう？

Finding and Maintaining Rigid Components

データ構造を頑張るやつ component が管理できる？

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment