All Questions
Tagged with perfect-matchings algorithms
14 questions
8
votes
1
answer
537
views
Fastest algorithm for counting perfect matchings in a general graph
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 ...
- 155
7
votes
1
answer
974
views
Algorithm to count the number of perfect matchings in non planar graph
I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
- 763
5
votes
6
answers
1k
views
Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs
I need to find all (up to isomorphism) perfect matchings of some quartic plane graphs. I haven't found any specific algorithm to give me all the perfect matchings. Does anybody know about such an ...
- 563
4
votes
2
answers
318
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 269
4
votes
1
answer
181
views
Algorithms to count perfect matchings in near planar graphs
It is well known that counting perfect matchings is tractable in planar graphs (due to Kastelyn).
I am interested in classes of (for lack of a better word) "near" planar graphs (1-planar, ...
- 129
4
votes
1
answer
189
views
Finding minimum weight perfect matchings in sparse bipartite graphs
Question:
What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?
I am looking for ...
- 13.2k
3
votes
1
answer
197
views
Is it possible to improve the weight of perfect bipartite matchings faster than with Bellman-Ford?
If $G\left(A\cup B,\ E=\lbrace\lbrace a, b\rbrace\,|\, a\in A,\, b\in B\rbrace\right)$ is a weighted bipartite graph and $M_0$ an initial perfect matching, then the optimality of $M_0$ can be verified ...
- 13.2k
3
votes
0
answers
88
views
Infection on a complete graph
Suppose we have a complete graph on $2n$ vertices with one "infected" vertex.
At each time step, we form a matching of the vertices. Then the vertices paired with infected vertices will also ...
1
vote
1
answer
62
views
Test Instances for Perfect Matchings in Graphs
Are there any graphs with a known set of perfect matchings and other predefined properties, such as vertex connectivity, which can be used for testing the implementation of matching algorithms?
...
- 13.2k
1
vote
2
answers
206
views
The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)
In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...
- 163
0
votes
3
answers
106
views
Calculating variance-minimal perfect matchings
Question:
are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?
- 13.2k
0
votes
1
answer
38
views
Edge-length constraints from greedy matching
The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.
The objective is to ...
- 13.2k
0
votes
0
answers
13
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 13.2k
0
votes
0
answers
48
views
Spanning subgraphs defined via $K_4$ matchings
I have by accident found an interesting kind of spanner of complete symmetric graphs $G(V,E)$ with weighted edges.
What I actually had planned was to implement an algorithm for calculating certain non-...
- 13.2k