TY - GEN
T1 - Steiner transitive-closure spanners of low-dimensional posets
AU - Berman, Piotr
AU - Bhattacharyya, Arnab
AU - Grigorescu, Elena
AU - Raskhodnikova, Sofya
AU - Woodruff, David P.
AU - Yaroslavtsev, Grigory
N1 - Funding Information:
E.G. is supported by NSF award CCR-0829672 and NSF award 1019343 to the Computing Research Association for the Computing Innovation Fellowship Program. S.R. and G.Y. are supported by NSF / CCF CAREER award 0845701. G.Y. is also supported by University Graduate Fellowship and College of Engineering Fellowship.
PY - 2011
Y1 - 2011
N2 - Given a directed graph G = (V,E) and an integer k ≥ 1, a Steiner k -transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H = (V H , E H ) such that (1) V ⊆ V H and (2) for all vertices v,u ε V, the distance from v to u in H is at most k if u is reachable from v in G, and ∞ otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted S k , of its sparsest Steiner k-TC-spanner. We present a nearly tight lower bound on S 2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on S k for d-dimensional posets.
AB - Given a directed graph G = (V,E) and an integer k ≥ 1, a Steiner k -transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H = (V H , E H ) such that (1) V ⊆ V H and (2) for all vertices v,u ε V, the distance from v to u in H is at most k if u is reachable from v in G, and ∞ otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted S k , of its sparsest Steiner k-TC-spanner. We present a nearly tight lower bound on S 2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on S k for d-dimensional posets.
UR - http://www.scopus.com/inward/record.url?scp=79960012949&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960012949&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22006-7_64
DO - 10.1007/978-3-642-22006-7_64
M3 - Conference contribution
AN - SCOPUS:79960012949
SN - 9783642220050
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 760
EP - 772
BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011
Y2 - 4 July 2011 through 8 July 2011
ER -