存在的复杂性加权循环
假设加权图G，顶点和边都被加权，并且给定常数k，以下决策问题A的复杂度是多少？
1-A：剂量 G 与总重量 K 的复烷循环？
2-如果 G 是平面图，A 的复杂度是多少？
也欢迎任何想法或指向论文或书籍！
Assume weighted Graph G, vertices and edges are weighted, and given constant k, what is the complexity of following decision problem A?
1-A: Dose G contane cycle with total weight K?
2- what is the complexity of A if G is a plannar graph?
Any idea or pointing to papers or book is also welcome!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
它是 NP 完全的，因为您可以从具有单位权重和 k=n 的平面 哈密顿循环 减少。
It is NP-complete, since you can reduce from planar Hamiltonian cycle with unit weights and k=n.