搜索结果: 1-5 共查到“数学 Perfect matchings”相关记录5条 . 查询时间(0.031 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：Perfect Matchings in hypergraphs
超图 完美匹配 图论
2023/4/27
Matchings are fundamental objects in the study of graph theory. Unlike in graphs, finding maximum matchings in general hypergraphs is NP-hard -- its decision problem is actually one of the Karp’s 21 N...
Edge-Removal and Non-Crossing Perfect Matchings
Edge-Removal Non-Crossing Matchings Combinatorics Probability
2011/9/5
Abstract: We study the following problem - How many arbitrary edges can be removed from a complete geometric graph with 2n vertices such that the resulting graph always contains a perfect non-crossing...
Exponentially many perfect matchings in cubic graphs
Exponentially many perfect matchings cubic graphs
2011/1/21
We show that every cubic bridgeless graph G has at least 2|V (G)|/3656 perfect matchings.
This confirms an old conjecture of Lov´asz and Plummer.
Computing the partition function for perfect matchings in a hypergraph
hypergraph perfect matching partition function permanent
2010/12/6
Given non-negative weights wS on the k-subsets S of a km-element set V , we consider the sum of the products wS1 · · ·wSm over all partitions V =S1 [ . . . [ Sm into pairwise disjoint k-subsets Si.
The covering radius problem for sets of perfect matchings
Perfect matchings Lovasz local lemma
2010/11/30
Consider the family of all perfect matchings of the complete graph K2n with 2n vertices.Given any collection M of perfect matchings of size s, there exists a maximum number f(n; x) such that if s f(...