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
Abstract:
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