29 Jan 10:15 Mikko Koivisto: Partitioning into Sets of Bounded Cardinality

HIIT seminar, Friday Jan 29, 10:15 a.m. (coffee from 10), Exactum B222

Dr. Mikko Koivisto
Helsinki Institute for Information Technology HIIT Department of Computer Science University of Helsinki

Partitioning into Sets of Bounded Cardinality

Research on moderately exponential time algorithms often deals with well-studied combinatorial objects, such as Hamiltonian cycles, dominating sets, graph colorings, and perfect matchings. In this talk, I will present a recent result that concerns the latter two, or more generally, set partitions.

We show that the partitions of an n-element set into k members of a given set family can be counted in time O(C^n), where C < 2 depends only on the maximum size among the members of the family. Specifically, we give a simple combinatorial algorithm that counts the perfect matchings in a given graph on n vertices in time O(poly(n) G^n), where G = 1.618... is the golden ratio; this improves a previous bound based on fast matrix multiplication.

Last updated on 1 Feb 2010 by Webmaster - Page created on 29 Jan 2010 by Visa Noronen