• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Counting the Number of Perfect Matchings in K5-Free Graphs
【24h】

Counting the Number of Perfect Matchings in K5-Free Graphs

机译：计数K5 - 自由图中完美匹配的数量

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Counting the number of perfect matchings in arbitrary graphs is a sharpP-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for K_{3, 3}-free graphs, Vazirani showed that it is in NC^2. The technique there is to compute a Pfaffian orientation of a graph. In the case of K_5-free graphs, this technique will not work because some K_5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K_5-free graphs can be computed in polynomial time and we describe a circuit construction in TC2.
机译：计算任意图中完美匹配的数量是一个锐利完整的问题。但是，对于一些限制的图表，问题可以有效地解决。在平面图的情况下，甚至对于K_ {3,3} -Free图，Vazirani表明它处于NC ^ 2中。该技术是计算图形的PFaffian方向。在k_5的图形的情况下，这种技术将不起作用，因为某些k_5无图没有PFaffian方向。我们规避了这个问题，并表明可以在多项式时间中计算K_5-Free图表中完美匹配的数量，并在TC2中描述了一种电路结构。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号