Questions tagged [matching-theory]
For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.
61 questions with no upvoted or accepted answers
1
vote
0
answers
299
views
On Schrijver's lower bound for the number of perfect matchings
Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...
- 13.9k
1
vote
0
answers
775
views
Is there an efficient algorithm to find all the maximum matching in any tree?
A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching of maximal cardinality. A tree is an acyclic connected graph.
Is there an efficient ...
1
vote
0
answers
77
views
Non-adjacent Pair of Edges with Minimal Weight Sum
Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that ...
- 13.2k
0
votes
0
answers
42
views
How to determine if two matchings are related by a permutation?
Let $n \geq 2$ be an integer. Let
\begin{align*}
V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\
E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}.
\end{align*}
...
- 5,215
0
votes
1
answer
168
views
How to understand Chegireddy-Hamacher's algorithm for finding k-best perfect matching
I am reading Algorithms for finding K-best perfect matchings by Chegireddy and Hamacher, and I have trouble to understand their Section 2 "General algorithm for K-best perfect matchings ". ...
- 163
0
votes
0
answers
65
views
Validity of an argument for an implication of NP-Completeness
Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges
As I see it the setting is a constrained bipartite matching and thus, ...
- 13.2k
0
votes
0
answers
110
views
Bound on the number of maximum matchings in a graph
It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...
- 2,089
0
votes
0
answers
71
views
A counterexample of a theorem about matching extendable
$M$ is perfect if $M$ covers all vertices of $G$, and $M$ is extendable if $G$ has a perfect matching containing $M$. Moreover, a graph $G$ with at least $2k + 2$ vertices is said to be $k$-extendable ...
- 1,851
0
votes
0
answers
26
views
Complexity of heaviest 2-optimal vertex-disjoint cycle covers
Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
- 13.2k
0
votes
0
answers
70
views
Birkhoff's theorem for hypergraphs
Birkhoff's theorem says that, in a bipartite graph $G$ in which both sides have size $n$, any fractional matching of size $n$ can be presented as a convex combination of integral matchings of size $n$ ...
- 3,549
0
votes
0
answers
58
views
Decomposition of triangle-free bridgeless planar cubic graphs
Question:
is it true that every triangle-free connected bridgeless planar cubic graph can be decomposed into a vertex-disjoint cycle cover and a single maximal matching of the edges that are adjacent ...
- 13.2k