Transitive-Closure Spanners

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung +2

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, E_H) that has (1) the same transitive-closure a…