论文标题
有效的枚举，以最小的多道路和多路切割
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
论文作者
论文摘要
令$ g =（v，e）$为无向图，让$ b \ subseteq v \ times v $为一组终端对。节点/edge Multiput是$ g $的顶点/边缘的子集，其删除摧毁了$ b $中每个终端对之间的所有路径。计算一个{\ em minimum}节点/边缘多图的问题是NP-固定的，并且从几个角度进行了广泛的研究。在本文中，我们研究了列举所有{\ em最小}节点多冲动的问题。我们给出了最小节点多冲动的增量多项式枚举算法，该算法扩展了由于Khachiyan等人的枚举算法。 （算法，2008年），用于最小的边缘多冲。节点/边缘多图的重要特殊情况是节点/edge {\ em multiway cuts}，其中一组终端对包含某些子集$ t \ subseteq v $中的每对顶点，也就是说，$ b = t \ t \ t \ t \ times t $ t $。我们改善了这种特殊情况的运行时间：我们设计了最小节点多路切割的多项式延迟和指数空间枚举算法，以及最小的边缘多路切口的多项式延迟和空间枚举算法。
Let $G = (V, E)$ be an undirected graph and let $B \subseteq V \times V$ be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of $G$ whose removal destroys all the paths between every terminal pair in $B$. The problem of computing a {\em minimum} node/edge multicut is NP-hard and extensively studied from several viewpoints. In this paper, we study the problem of enumerating all {\em minimal} node multicuts. We give an incremental polynomial delay enumeration algorithm for minimal node multicuts, which extends an enumeration algorithm due to Khachiyan et al. (Algorithmica, 2008) for minimal edge multicuts. Important special cases of node/edge multicuts are node/edge {\em multiway cuts}, where the set of terminal pairs contains every pair of vertices in some subset $T \subseteq V$, that is, $B = T \times T$. We improve the running time bound for this special case: We devise a polynomial delay and exponential space enumeration algorithm for minimal node multiway cuts and a polynomial delay and space enumeration algorithm for minimal edge multiway cuts.
