「这玩意可以用来做多项式时间复杂度的半哈密顿图求解？」 - 洛谷帖子保存站

这玩意可以用来做多项式时间复杂度的半哈密顿图求解？

板块P2764 最小路径覆盖问题
楼主ipLee
当前回复4
已保存回复4
发布时间2021/8/20 01:04
上次更新2023/11/4 09:58:16

被骇客银狼阻止的越权访问保存失败

这玩意可以用来做多项式时间复杂度的半哈密顿图求解？

ipLee楼主2021/8/20 01:04

这个如果能求出来只有一条路径覆盖，那就说明原图是半哈密顿图，否则就不是。。。感觉没问题？但是不是说哈密顿问题是NP的吗

2021/8/20 01:04