一般为 NP 困难但在平面图中具有多项式时间解的问题列表？
我遇到了很多可以表述为图形问题的问题。 它通常是 NP 困难的，但有时可以证明该图是平面的。 因此，我对学习这些问题和算法很感兴趣。
据我所知：
- 平面图中的最大割 平面图
- 中的四色 平面图
- 中的最大独立集
希望有人可以完成此列表。
I encountered many problems that can be formulated as graph problem.
It is in general NP-hard but sometimes the graph can be proved to be planar.
Hence, I am interested in learning these problems and the algorithms.
So far as I know:
- Max cut in planar graphs
- Four-coloring in planar graphs
- Max Independent Set in cubic planar graphs
Hope someone can complete this list.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在这个纲要中的NP完全问题，在平面下在索引中有大量（~25）的条目。这些条目通常涉及平面输入允许 PTAS 的问题。
In this compendium of NP-complete problems, under planar in the index there are a good number (~25) of entries. These entries typically link to problems where planar input admits a PTAS.