BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20200329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20191027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20200125T152649Z
UID:5d97073d3a999511839247@ist.ac.at
DTSTART:20191115T110000
DTEND:20191115T120000
DESCRIPTION:Speaker: Taihei Oki\nhosted by Vladimir Kolmogorov\nAbstract: T
he celebrated matrix-tree theorem\, which is to count the number of spanni
ng trees in graphs\, is a theorem essentially for counting bases of genera
l regular matroids. Webb (2004) introduced the notion of Pfaffian pairs as
a pair of regular matroids for which counting of their common bases is tr
actable through the matrix-tree theorem. This class can represent a bunch
of important combinatorial structures\, such as spanning trees\, arboresce
nces\, 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-tre
e theorem for Pfaffian pairs\, we present deterministic polynomial-time al
gorithms for several counting problems: exact\, group-labeled and weighted
problem settings.
LOCATION:Mondi Seminar Room 3\, Central Building\, IST Austria
ORGANIZER:kharppre@ist.ac.at
SUMMARY:A generalized matrix-tree theorem for Pfaffian pairs
URL:https://talks-calendar.app.ist.ac.at/events/2353
END:VEVENT
END:VCALENDAR