Polynomial-Delay Enumeration of Large Maximal Matchings / 大きな極大マッチングの多項式遅延列挙
- Resource Type
- Journal Article
- Authors
- Kazuhiro KURITA; Kunihiro WASA; Yasuaki KOBAYASHI; 和佐 州洋; 小林 靖明; 栗田 和宏
- Source
- Proceedings of the Annual Conference of JSAI. 2021, :2
- Subject
- Enumeration
Maximal matching
Size constraint
サイズ制約
列挙
極大マッチング
- Language
- Japanese
We present polynomial-delay enumeration algorithms for maximal matchings with cardinality at least given threshold t. The first algorithm enumerates all such matchings in O(m2) delay, where m is the number of edges of an input graph. This extends known results for enumerating maximal matchings to the cardinality constrained problem. The second algorithm enumerates all maximal matchings in non-ascending order of its cardinality and runs in polynomial delay.