Shallow excluded minors and improved graph decompositions
Shallow excluded minors and improved graph decompositions
复制标题
浅层排除未成年人并改进图分解
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Warren D. Smith
中科院分区：
文献类型：
--
作者：
Serge A. Plotkin;Satish Rao;Warren D. Smith
在本文中，我们介绍了有限深度次要排除的概念，并表明排除小的有限深度次要排除的图具有相对较小的分隔符。特别是，我们证明对于任何排除 Kh 作为深度 l 小数的图，我们可以找到大小为 O(lh2 logn + n=l) 的分隔符。反过来，这意味着任何排除 Kh 作为次要的图都有一个 O(hpn logn) 大小的分隔符，从而改进了 Alon、Seymour 和 Thomas 对于 h plogn 的情况的结果。我们证明，当 d 是常数时，由 Miller 和 Thurston 定义的具有恒定长宽比的 d 维单纯图排除了深度 L 的 Kh 次要，因为 h = (Ld 1)。这些图出现在有限元计算中。我们对分隔符存在性的证明是建设性的，并给出了一种在排除小深度次要的图中找到 t-cut-covers 分解的算法，该算法由 Kaklamanis、Krizanc 和 Rao 提出。这有两个有趣的含义。首先，我们的 t-cut-cover 算法与 Kaklamanis 等人的结果相结合，给出了一种在超立方并行计算机上以渐近最大加速实现三个或更多维度的许多有限元计算的方法。其次，通过将 t-cut-cover 算法与 Leiserson、Rao 和 Toledo 开发的技术相结合，给出了一种算法，可以渐进地改善任何三维或更多维度的核外线性松弛有限元计算所使用的外部存储器流量。
In this paper we introduce the notion of the limited-depth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that for any graph that excludes Kh as a depth l minor, we can find a separator of size O(lh2 logn + n=l). This, in turn, implies that any graph that excludes Kh as a minor has an O(hpn logn)-sized separator, improving the result of Alon, Seymour, and Thomas for the case where h plogn. We show that the d-dimensional simplicial graphs with constant aspect ratio, defined by Miller and Thurston, exclude Kh minors of depth L for h = (Ld 1) when d is a constant. These graphs arise in finite element computations. Our proof of separator existence is constructive and gives an algorithm to find the t-cut-covers decomposition, introduced by Kaklamanis, Krizanc, and Rao, in graphs that exclude small depth minors. This has two interesting implications. First, combination of our t-cut-cover algorithm with the results of Kaklamanis et al., gives a way to implement many finite element computations in three or more dimensions on a hypercubic parallel computer with asymptotically maximal speedup. Second, by combining the t-cut-cover algorithm with the techniques developed by Leiserson, Rao and Toledo, gives an algorithm to asymptotically improve the external memory traffic used by any out-of-core linear relaxation finite element computation in three or more dimensions.