9:40 AM - 10:00 AM
[2E1-OS-13a-03] Polynomial-Delay Enumeration of Large Maximal Matchings
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.