Transitive-Closure Spanners
Transitive-Closure Spanners
复制标题
传递闭包扳手
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Elena Grigorescu;Kyomin Jung;Sofya Raskhodnikova;David P. Woodruff
给定一个有向图$G=(V，E)$和一个整数$kgeq1$，$G$的$k$传递闭包扳手($k$-TC-spanner)是一个有向图$H=(V，E_H)$，它具有(1)与$G$相同的传递闭包，(2)直径至多为$k$.这些扳手是在电路复杂性、数据结构、性能测试和访问控制的背景下隐含地进行研究的，并且在20年的时间里重新发现了这些扳手的属性。我们将这些不同应用中隐含处理的常见任务抽象为构造稀疏TC-spanner的问题。我们开始了对给定有向图的最稀疏$k$-TC-扳手大小的逼近性的研究。我们完全解决了$2$-TC-spanner的逼近性，证明了它是$theta(Logn)$，除非$extsf{P}=extsf{NP}$。对于$k>；2$，我们给出了一个多项式时间算法，它可以找到一个$k$-TC-spanner，它的大小在$O((Nlogn)^{1-1/k})$内。我们的技术也产生了第一个非平凡的应用程序的算法。
Given a directed graph $G = (V,E)$ and an integer $k geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest $k$-TC-spanner of a given directed graph. We completely resolve the approximability of $2$-TC-spanners, showing that it is $Theta(log n)$ unless $ extsf{P} = extsf{NP}$. For $k>2$, we present a polynomial time algorithm that finds a $k$-TC-spanner with size within $O((n log n)^{1-1/k})$ of the optimum. Our techniques also yield algorithms with the first nontrivial app...