All Questions

Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...

Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices). ...

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...

Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$? The problem of computing all perfect matchings is #P-complete. But I ...

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 ...