论文标题
某些经典图形问题的NP完整变体
NP-complete variants of some classical graph problems
论文作者
论文摘要
可以有效地完成一些经典的图形问题，例如查找最小跨越树，最短路径或最大流量。我们描述了这些问题的轻微变化，这些问题被证明是NP完整的。我们的证明使用$ 3 $ -SAT的直接减少。
Some classical graph problems such as finding minimal spanning tree, shortest path or maximal flow can be done efficiently. We describe slight variations of such problems which are shown to be NP-complete. Our proofs use straightforward reduction from $3$-SAT.
