Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-
TCspanner) 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 access control, property
testing, and data structures, and properties of these spanners have been rediscovered over
the span of 20 years. We bring these areas under the unifying framework of TC-spanners.
Lecture Notes
Home > Activities > Outputs > Lecture Notes
Title 
JungKyomin.pptx