Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
复制标题
用于列出图的最小顶点分隔符的空间最优回溯算法
DOI：
10.1016/j.dam.2010.05.013
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Kenshiro Takata
中科院分区：
文献类型：
--
作者：
Kenshiro Takata
对于位于 n 个顶点和 m 个边的只读存储器中的图 G 以及一个只写输出缓冲区，我们给出了两种仅使用 O(n) 可重写空间的算法。第一个算法列出了 G 的所有最小 a−b 分隔符，多项式延迟为 O(nm)。第二个列出了 G 的所有最小顶点分隔符，累积多项式延迟为 O(n3m)。一个结果是算法可以列出每个对象输出花费 O(nm) 时间（分别为 O(n3m) 时间）的最小 a−b 分隔符（和最小顶点分隔符）。
For a graph G in read-only memory on n vertices and m edges and a write-only output buffer, we give two algorithms using only O(n) rewritable space. The first algorithm lists all minimal a−b separators of G with a polynomial delay of O(nm). The second lists all minimal vertex separators of G with a cumulative polynomial delay of O(n3m). One consequence is that the algorithms can list the minimal a−b separators (and minimal vertex separators) spending O(nm) time (respectively, O(n3m) time) per object output.