TY - GEN
T1 - Transitive-closure spanners
T2 - Mini-Workshop on Property Testing
AU - Raskhodnikova, Sofya
PY - 2010/11/24
Y1 - 2010/11/24
N2 - We survey results on transitive-closure spanners and their applications. Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive- closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH ) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in different areas of computer science, and properties of these spanners have been rediscovered over the span of 20 years. The common task implicitly tackled in these diverse applications can be abstracted as the problem of constructing sparse TC-spanners. In this article, we survey combinatorial bounds on the size of sparsest TC-spanners, and algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph. We also describe multiple applications of TC-spanners, including property testing, property reconstruction, key management in access control hierarchies and data structures.
AB - We survey results on transitive-closure spanners and their applications. Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive- closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH ) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in different areas of computer science, and properties of these spanners have been rediscovered over the span of 20 years. The common task implicitly tackled in these diverse applications can be abstracted as the problem of constructing sparse TC-spanners. In this article, we survey combinatorial bounds on the size of sparsest TC-spanners, and algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph. We also describe multiple applications of TC-spanners, including property testing, property reconstruction, key management in access control hierarchies and data structures.
UR - https://www.scopus.com/pages/publications/78449291504
UR - https://www.scopus.com/pages/publications/78449291504#tab=citedBy
U2 - 10.1007/978-3-642-16367-8_10
DO - 10.1007/978-3-642-16367-8_10
M3 - Conference contribution
AN - SCOPUS:78449291504
SN - 3642163661
SN - 9783642163661
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 167
EP - 196
BT - Property Testing - Current Research and Surveys
Y2 - 8 January 2010 through 10 January 2010
ER -