Treewidth Computation and Kernelization in the Parallel External Memory Model
Treewidth Computation and Kernelization in the Parallel External Memory Model
复制标题
并行外部存储器模型中的树宽计算和核化
DOI：
10.1007/978-3-662-44602-7_7
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Matthias Mnich
中科院分区：
文献类型：
--
作者：
Tobias Lieber;Matthias Mnich
我们提出了一种随机算法，对于任何固定的k，计算任何输入图的宽度至多k的树分解。我们在并行外部存储器 (PEM) 模型中对其进行分析，该模型通过计算多 CPU 专用缓存共享内存机器上的缓存未命中次数来衡量效率。我们的算法具有排序复杂性，我们证明它对于大参数范围来说是最佳的。我们使用该算法作为 PEM 高效核化算法的一部分。核化是一种通过将具有结构参数 κ 的大小为 NP 难题的实例有效地压缩到内核（大小至多为 g(κ) 的等效实例）来预处理它们的技术。然后可以从内核的最优解有效地恢复原始实例的最优解。我们的主要结果是 Fomin 等人提出的线性时间随机突出替换算法的改编。 （FOCS 2012）。特别是，我们获得了高效的随机并行算法来计算 PEM 模型中的线性核，适用于顶点无小图上具有有限整数索引 (FII) 的所有可分离收缩二维问题，以及拓扑无小图上具有 FII 的所有树宽边界图问题。
We present a randomized algorithm which computes, for any fixedk, a tree decomposition of width at mostkof any input graph. We analyze it in the parallel external memory (PEM) model that measures efficiency by counting the number of cache misses on a multi-CPU private cache shared memory machine. Our algorithm has sorting complexity, which we prove to be optimal for a large parameter range.We use this algorithm as part of a PEM-efficient kernelization algorithm. Kernelization is a technique for preprocessing instances of sizenofNP-hard problems with a structural parameterκby compressing them efficiently to a kernel, an equivalent instance of size at mostg(κ). An optimal solution to the original instance can then be recovered efficiently from an optimal solution to the kernel. Our main results here is an adaption of the linear-time randomized protrusion replacement algorithm by Fomin et al. (FOCS 2012). In particular, we obtain efficient randomized parallel algorithms to compute linear kernels in the PEM model for all separable contraction-bidimensional problems with finite integer index (FII) on apex minor-free graphs, and for all treewidth-bounding graph problems with FII on topological minor-free graphs.
登录
查看更多内容
细分层次结构的并行构建
DOI：
--
发表时间：
1989
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
Norm Dadoun;D. Kirkpatrick
通讯作者：
D. Kirkpatrick
有界树宽图的 I/O 高效算法
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
A. Maheshwari;N. Zeh
通讯作者：
N. Zeh
DOI：
10.1007/978-3-662-44465-8_33
发表时间：
2014-06
期刊：
--
影响因子：
--
作者：
R. Jacob;T. Lieber;Nodari Sitchinava
通讯作者：
R. Jacob;T. Lieber;Nodari Sitchinava
DOI：
10.1007/978-3-642-28050-4_15
发表时间：
2011-09
期刊：
--
影响因子：
--
作者：
T. Hagerup
通讯作者：
T. Hagerup
图的路径宽度和树宽度的高效且有建设性的算法
DOI：
10.1006/jagm.1996.0049
发表时间：
1993
期刊：
J. Algorithms
影响因子：
--
作者：
H. Bodlaender;T. Kloks
通讯作者：
T. Kloks