Steiner transitive-closure spanners of low-dimensional posets

DOI10.1007/s00493-014-2833-9zbMath1363.05094arXiv1011.6100OpenAlexW3022165982MaRDI QIDQ397071

Elena Grigorescu, David P. Woodruff, Sofya Raskhodnikova, Piotr Berman, Arnab Bhattacharyya, Grigory Yaroslavtsev

Publication date: 14 August 2014

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.6100

zbMATH Keywords

posetsgraphsTC-spanner

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Tight bounds to localize failure nodes on trees, grids and through embeddings under Boolean network tomography ⋮ Weighted \(L_{\infty}\) isotonic regression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property-preserving data reconstruction
• New constructions for provably-secure time-bound hierarchical key assignment schemes
• Unbounded fan-in circuits and associative functions
• Computing on a free tree via complexity-preserving mappings
• On the dimensions of ordered sets of bounded degree
• The dimension of planar posets
• Steiner Transitive-Closure Spanners of Low-Dimensional Posets
• Parallel Shortcutting of Rooted Trees
• The Complexity of the Partial Order Dimension Problem
• Graph spanners
• Shortcutting Planar Digraphs
• Transitive-Closure Spanners
• Transitive-Closure Spanners: A Survey
• Local Monotonicity Reconstruction
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• Concerning similarity transformations of linearly ordered sets
• Partially Ordered Sets
• Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
• On the dimension of partially ordered sets

This page was built for publication: Steiner transitive-closure spanners of low-dimensional posets