Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs
复制标题
DOI：
10.1007/3-540-19488-6_149
复制
发表时间：
1988-07
期刊：
影响因子：
--
通讯作者：
V. Vazirani;M. Yannakakis
中科院分区：
文献类型：
--
作者：
V. Vazirani;M. Yannakakis
计算复杂性中的以下问题仍然没有得到准确的理解：尽管矩阵的积式和行列式的公式看起来相似，但计算它们的复杂性存在显着差异，检查有向图是否包含偶数长度循环的复杂性，以及计算的复杂性完美匹配的数量使用普法菲定向的图。通过多项式时间等价，我们显示这些问题之间的相互关系。
The following issues in computational complexity remain imprecisely understood: the striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, the complexity of checking if a directed graph contains an even length cycle, and the complexity of computing the number of perfect matchings in a graph using Pfaffian orientations. Via polynomial time equivalences, we show interrelationships among these issues.