All Questions

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree. MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...

Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$...

Planar graph permanent can be reduced to determinants and so statistics should be amenable. Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional ...