论文标题
列出图表的最小分离器
Listing Small Minimal Separators of a Graph
论文作者
论文摘要
令$ g $为$ g $的$ a，$ a，b $顶点。 $ g $的最小$ a，b $ - 分类者是包含在包含的最小顶点$ g $的$ a $ a $和$ b $的最小顶点。我们认为，给定一些整数$ k $，列举了最多包含$ k $ vertices的最小$ a，b $ g $的最低$ a，b $ g $。我们给出了一种列举列出这样的最小分离器，最多最多$ poly（n）r \ cdot \ min \ min（4^k，r）$ $ $ $ r $输出了第一个$ r $ r $最小的分离器。因此，我们的算法可以归类为固定参数 - 延迟和增量多项式时间。据我们所知，以前没有针对此问题发表过非平凡时间复杂性的算法。我们还讨论获得多项式 - 延迟算法的障碍。
Let $G$ be a graph and $a,b$ vertices of $G$. A minimal $a,b$-separator of $G$ is an inclusion-wise minimal vertex set of $G$ that separates $a$ and $b$. We consider the problem of enumerating the minimal $a,b$-separators of $G$ that contain at most $k$ vertices, given some integer $k$. We give an algorithm which enumerates such minimal separators, outputting the first $R$ minimal separators in at most $poly(n) R \cdot \min(4^k, R)$ time for all $R$. Therefore, our algorithm can be classified as fixed-parameter-delay and incremental-polynomial time. To the best of our knowledge, no algorithms with non-trivial time complexity have been published for this problem before. We also discuss barriers for obtaining a polynomial-delay algorithm.
