Campus Event Calendar
Event Entry
What and Who
Count perfect matchings in planar graphs
Mingji Xia
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 26 September 2013
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
The number of perfect matchings in planar graphs can be computed in polynomial time. The gadgets in this #Pl-PM problem are called matchgate, whose functions satisfy some identities. The famous FKT algorithm for #Pl-PM and the known matchgate identities, are based on the algorithm and Grassmann-Plücker identities of Pfaffian, respectively.
We prove the matchgate identities in a simpler way, by showing the functions of matchgates are in a closed set generated by two growth operations, called juxtaposition and jumper by Matthew Cook. Because of these identities, instead of all exponentially many values, polynomial many values are enough to record a matchgate function. These facts give a #Pl-PM algorithm directly. Using the known matchgate that simulates crossing, this new algorithm can be adapted to both Pfaffian and Determinant.
Contact
Mengji Xia
--email hidden
passcode not visible
logged in users only
Mengji Xia, 09/25/2013 16:37
Mengji Xia, 09/25/2013 16:36 -- Created document.
Mengji Xia, 09/25/2013 16:36 -- Created document.