加载中…
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves on a previous degree bound of . Our NP-completeness result holds even for subcubic graphs that are planar.

生成讲解博客的中文版本

生成AI智能校验的中文版本