[2E1-OS-13a] AIと制約プログラミング(1/3)

[2E1-OS-13a-03] Polynomial-Delay Enumeration of Large Maximal Matchings

〇Kazuhiro Kurita¹, Yasuaki Kobayashi², Kunihiro Wasa³ (1. National Institute of Informatics, 2. Kyoto University, 3. Toyohashi University of Technology)

Keywords:Enumeration, Maximal matching, Size constraint

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(m²) 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.