论文标题
边缘多路切割和节点多路切割在亚立管图上是NP完整的
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
论文作者
论文摘要
我们表明，边缘多路切割（也称为多通用切割），节点多路路切割在最高度$ 3 $的图表上是NP完整的（也称为亚采比图）。这在先前的学位上有所改善，$ 11 $。我们的NP完整性结果即使对于平面的亚地铁图也成立。
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves on a previous degree bound of $11$. Our NP-completeness result holds even for subcubic graphs that are planar.
