Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
复制标题
计算四次 4 顶点连接平面图上的哈密顿循环
DOI：
10.1007/s00373-019-02101-7
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
R. D. Barish and A. Suyama
中科院分区：
文献类型：
--
作者：
Hasan M;Hama S;Kogure K.;R. D. Barish and A. Suyama;R. D. Barish and A. Suyama
我们证明了在多次计数（“弱简约”）约简下，四次4顶点连通平面图上的哈密顿环计数是完全的，并且对于这个整数计数问题不存在完全多项式时间随机化近似方案（FPRAS），除非。
We show that counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs is-complete under many-one counting (“weakly parsimonious”) reductions, and that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) can exist for this integer counting problem unless.