首页> 外文会议>International Colloquium on Automata, Languages and Programming >Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

【24h】

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

机译：在O（n）预期时间内的稀疏随机图中找到最大匹配

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor.

机译：我们提出了一种线性预期时间算法，用于在稀疏随机图中查找最大基数匹配。这是最佳的，并通过对数因子提高先前的结果。

著录项

来源
《International Colloquium on Automata, Languages and Programming 》|2008年||共12页
会议地点
作者
Prasad Chebolu; Alan Frieze; Pall Melsted;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类 TP3-53;
关键词

相似文献

外文文献
中文文献
专利

1. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time [J] . PRASAD CHEBOLU, ALAN FRIEZE, PALL MELSTED Journal of the Association for Computing Machinery . 2010 ,第4期

机译：在O（n）预期时间的稀疏随机图中找到最大匹配项
2. Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs [J] . Naparstek Oshri, Leshem Amir Random structures & algorithms . 2016 ,第2期

机译：随机图上最大二部匹配的拍卖算法和推式重标记算法的预期时间复杂度
3. Finding Maximum Induced Matchings in Subclasses of Claw-Free and P_5-Free Graphs, and in Graphs with Matching and Induced Matching of Equal Maximum Size [J] . Daniel Kobler, Udi Rotics Algorithmica . 2003 ,第4期

机译：在无爪图和无P_5图的子类中以及在具有相等且最大大小相等的匹配和归纳匹配的图中查找最大诱导匹配
4. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time [C] . Prasad Chebolu, Alan Frieze, Pall Melsted International Colloquium on Automata, Languages and Programming;ICALP 2008 . 2008

机译：在O（n）预期时间内在稀疏随机图中找到最大匹配项
5. Colorings, Matchings and Packings in Random and Pseudo-Random Graphs [D] . Bal, Deepak 2013

机译：随机图和伪随机图的着色，匹配和堆积
6. Finding a Maximum Common Subgraphfrom Molecular StructuralFormulas through the Maximum Clique Approach Combined with the IsingModel [O] . Yasuharu Okamoto 2020

机译：查找最大公共子图来自分子结构通过最大派系方法与Ising结合的公式模型
7. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time [O] . Chebolu, Prasad, Frieze, Alan, Melsted, Pall 2012

机译：在O（n）预期时间的稀疏随机图中找到最大匹配项
8. Large Matchings and Cycles in Sparse Random Graphs [R] . Frieze, A. M. 1984

机译：稀疏随机图中的大匹配和周期

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

摘要

著录项

相似文献

相关主题

期刊订阅