Transitive-Closure Spanners: A Survey
From MaRDI portal
Publication:4933368
DOI10.1007/978-3-642-16367-8_10zbMath1309.68155OpenAlexW1492237614MaRDI QIDQ4933368
Publication date: 12 October 2010
Published in: Property Testing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_10
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items
Dynamic Tree Shortcut with Constant Degree ⋮ Steiner transitive-closure spanners of low-dimensional posets ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Steiner Transitive-Closure Spanners of Low-Dimensional Posets ⋮ Limitations of Local Filters of Lipschitz and Monotone Functions ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Information theory in property testing and monotonicity testing in higher dimension
- Property-preserving data reconstruction
- Computing on a free tree via complexity-preserving mappings
- On sparse spanners of weighted graphs
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- On the strength of comparisons in property testing
- The hardness of approximating spanner problems
- A decomposition theorem for partially ordered sets
- Compact Routing with Minimum Stretch
- Finding sparser directed spanners
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Steiner Transitive-Closure Spanners of Low-Dimensional Posets
- Parallel Shortcutting of Rooted Trees
- Property testing and its connection to learning and approximation
- Efficient Provably-Secure Hierarchical Key Assignment Schemes
- Approximate distance oracles
- Monotonicity testing over general poset domains
- The Complexity of the Partial Order Dimension Problem
- Graph spanners
- A Separator Theorem for Planar Graphs
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Distributed Computing: A Locality-Sensitive Approach
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact roundtrip routing in directed networks
- Shortcutting Planar Digraphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Transitive-Closure Spanners
- Object location using path separators
- Automata, Languages and Programming
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- The Transitive Reduction of a Directed Graph
- Concerning similarity transformations of linearly ordered sets
- Computing almost shortest paths
- Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
- Testing monotonicity
- On the hardness of approximating spanners
