JSAI2021

Presentation information

Organized Session

Organized Session » OS-13

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

Wed. Jun 9, 2021 9:00 AM - 10:40 AM Room E (OS room 3)

座長:宋 剛秀(神戸大学)

9:40 AM - 10:00 AM

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

〇Kazuhiro Kurita1, Yasuaki Kobayashi2, Kunihiro Wasa3 (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(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.

Authentication for paper PDF access

A password is required to view paper PDFs. If you are a registered participant, please log on the site from Participant Log In.
You could view the PDF with entering the PDF viewing password bellow.

Password