...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The combinatorial approach yields an NC algorithm for computing Pfaffians
【24h】

The combinatorial approach yields an NC algorithm for computing Pfaffians

机译：组合方法产生了用于计算Pfaffians的NC算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Pfaffian of an oriented graph is closely linked to perfect matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and determinant is usually exploited to give a fast algorithm for computing Pfaffians. We present the first NC algorithm for computing the Pfaffian. (Previous determinant-based methods computed it in NC only up to the correct sign, while previous polynomial-time algorithms did not lend themselves to parallelization.) Our algorithm is completely combinatorial in nature. Furthermore, it is division-free and works over arbitrary commutative rings. Over integers, we show that it can be implemented in the complexity class GapL. This upper bound was not known before, and establishes that computing the Pfaffian for integer skew-symmetric matrices is complete for GapL. Our proof techniques generalize the recent combinatorial characterization of determinant Proceedings of the Eighth Annual ACM-SIAM Symposium o Discrete Algorithms, SODA, 1997, 730. As a corollary, we show that under reasonable encodings of a planar graph, Kasteleyn's algorithm [Graph Theory and Theoretical Physics, Academic Press, New York, 1967, 43] for counting the number of perfect matchings in a planar graph is also in GapL. (C) 2003 Elsevier B.V. All rights reserved.
机译：有向图的Pfaffian与完美匹配紧密相关。它自然也与适当定义的矩阵的行列式有关。通常利用Pfaffian与行列式之间的这种关系来提供一种快速的算法来计算Pfaffian。我们提出了用于计算Pfaffian的第一个NC算法。 （以前的基于行列式的方法只能在NC中将其计算到正确的符号，而先前的多项式时间算法无法使其并行化。）我们的算法本质上是完全组合的。此外，它是无除法的，并且可以在任意交换环上工作。在整数上，我们表明可以在复杂性类GapL中实现它。这个上限以前是未知的，并确定对于GapL，完成整数斜对称矩阵的Pfaffian计算是完整的。我们的证明技术概括了第八届年度ACM-SIAM离散算法研讨会（SODA，1997，730）行列式程序的最近组合特征。作为推论，我们证明了在平面图的合理编码下，Kasteleyn算法[图论和GapL中也提供了理论物理学，纽约，学术出版社，1967年，第43页]。 （C）2003 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号