English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a directed graph G and an integer k >= 1, ak-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has(1) the same transitive-closure as G and (2) diameter at most k. In someapplications, the shortcut paths added to the graph in order to obtain smalldiameter can use Steiner vertices, that is, vertices not in the original graphG. The resulting spanner is called a Steiner transitive-closure spanner(Steiner TC-spanner).  Motivated by applications to property reconstruction and access controlhierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphsor, equivalently, partially ordered sets. In these applications, the goal is tofind a sparsest Steiner k-TC-spanner of a poset G for a given k and G. Thefocus of this paper is the relationship between the dimension of a poset andthe size of its sparsest Steiner TCspanner. The dimension of a poset G is thesmallest d such that G can be embedded into a d-dimensional directed hypergridvia an order-preserving embedding.  We present a nearly tight lower bound on the size of Steiner 2-TC-spanners ofd-dimensional directed hypergrids. It implies better lower bounds on thecomplexity of local reconstructors of monotone functions and functions with lowLipschitz constant. The proof of the lower bound constructs a dual solution toa linear programming relaxation of the Steiner 2-TC-spanner problem. We alsoshow that one can efficiently construct a Steiner 2-TC-spanner, of sizematching the lower bound, for any low-dimensional poset. Finally, we present alower bound on the size of Steiner k-TC-spanners of d-dimensional posets thatshows that the best-known construction, due to De Santis et al., cannot beimproved significantly.

Steiner Transitive-Closure Spanners of d-Dimensional Posets