Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs
Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs
复制标题
随机二部图中左完美匹配的最优度分布
DOI：
10.1007/s00224-014-9577-1
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
Michael Rink
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Michael Rink
考虑一个随机二部多重图G，G的左结点数为n，右结点数为m ≥n≥2.每个左节点有dx ≥1个随机右邻居。平均左度数Δ是固定的，Δ≥2。我们问，对于G具有左完美匹配的概率，不为每个左节点固定dx，而是根据某种（巧妙选择的）分布随机选择dx，是否有利。假设左节点的度是独立的，我们证明如下：如果Δ是一个整数，那么对所有左节点使用一个固定的度Δ是最优的。如果Δ是非整数的，那么最优度分布具有这样的性质：每个左节点有两个可能的度，分别是概率为px和1−px的Δ和Δ，其中px来自闭区间[0，1]，所有px的平均值等于Δ −Δ。此外，如果c =n/mand Δ>2是常数，则满足上述条件的每个左度分布确定了相同的阈值dk（Δ），该阈值dk（Δ）具有以下性质：如果c <c dk（Δ）则渐近几乎必然存在左完美匹配。如果c>c（Δ），则渐近几乎必然不存在左完美匹配。对于整数或非整数k =Δ，阈值dk（Δ）与离线k元cuckoo散列的已知阈值相同。
Consider a random bipartite multigraphGwithnleft nodes andm≥n≥2 right nodes. Each left nodexhasdx≥1 random right neighbors. The average left degree Δ is fixed, Δ≥2. We ask whether for the probability thatGhas a left-perfect matching it is advantageous not to fixdxfor each left nodexbut rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If Δ is an integer, then it is optimal to use a fixed degree of Δ for all left nodes. If Δ is non-integral, then an optimal degree-distribution has the property that each left nodexhas two possible degrees, ⌊Δ⌋ and ⌈Δ⌉, with probabilitypxand 1−px, respectively, wherepxis from the closed interval [0,1] and the average over allpxequals ⌈Δ⌉−Δ. Furthermore, ifc=n/mand Δ>2 are constant, then each distribution of the left degrees that meets the conditions above determines the same thresholdc∗(Δ) that has the following property asngoes to infinity: Ifc<c∗(Δ) then asymptotically almost surely there exists a left-perfect matching. Ifc>c∗(Δ) then asymptotically almost surely there exists no left-perfect matching. The thresholdc∗(Δ) is the same as the known threshold for offlinek-ary cuckoo hashing for integral or non-integralk=Δ.
登录
查看更多内容
布谷鸟哈希的急剧负载阈值
影响因子：
1
作者：
N. Fountoulakis;K. Panagiotou
通讯作者：
K. Panagiotou
随机二部图中的最大匹配与布谷鸟哈希表的空间利用率
DOI：
--
发表时间：
2009
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
A. Frieze;Páll Melsted
通讯作者：
Páll Melsted
用于线性时间构造更密集的基于散列的数据结构的混合超图
DOI：
10.1007/978-3-642-35843-2_31
发表时间：
2013
期刊：
影响因子：
--
作者：
Michael Rink
通讯作者：
Michael Rink
随机超图的可定向性和多重选择的力量
DOI：
--
发表时间：
2010
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
N. Fountoulakis;K. Panagiotou
通讯作者：
K. Panagiotou