Nov 15, 2019

A generalized matrix-tree theorem for Pfaffian pairs

Date: November 15, 2019 | 11:00 am – 12:00 pm
Speaker: Taihei Oki, University of Tokyo
Location: Mondi Seminar Room 3, Central Building

The celebrated matrix-tree theorem, which is to count the number of spanning trees in graphs, is a theorem essentially for counting bases of general regular matroids. Webb (2004) introduced the notion of Pfaffian pairs as a pair of regular matroids for which counting of their common bases is tractable through the matrix-tree theorem. This class can represent a bunch of important combinatorial structures, such as spanning trees, arborescences, Euler tours in 4-regular digraphs and perfect matchings in K_{3,3}-free bipartite graphs. In this talk, as an application of the matrix-tree theorem for Pfaffian pairs, we present deterministic polynomial-time algorithms for several counting problems: exact, group-labeled and weighted problem settings.

More Information:

Date:
November 15, 2019
11:00 am – 12:00 pm

Speaker:
Taihei Oki, University of Tokyo

Location:
Mondi Seminar Room 3, Central Building

Contact:

HARPPRECHT Ksenja

Email:
kharppre@ist.ac.at

Share



Back to Top