首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Derandomizing Isolation Lemma for K 3 3 -free and K 5 -free Bipartite Graphs
  • 本地全文:下载
  • 作者:Rahul Arora ; Ashu Gupta ; Rohit Gurjar
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The perfect matching problem has a randomized N C algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We derandomize this lemma for K 3 3 -free and K 5 -free bipartite graphs, i.e. we give a deterministic log-space construction of such a weight assignment for these graphs. Such a construction was known previously for planar bipartite graphs. Our result implies that the perfect matching problem for K 3 3 -free and K 5 -free bipartite graphs is in SPL .

  • 关键词:Bipartie Matching ; derandomization ; Isolation Lemma ; K33-free ; K5-free ; SPL
国家哲学社会科学文献中心版权所有