Transitive-Closure Spanners

DOI10.1137/110826655zbMath1261.68094OpenAlexW2071769989MaRDI QIDQ4910569

Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff, Arnab Bhattacharyya

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110826655

zbMATH Keywords

approximation algorithmsspannershardness of approximationgraph separators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (23)

Testing Lipschitz functions on hypergrid domains ⋮ Parameterized property testing of functions ⋮ Steiner transitive-closure spanners of low-dimensional posets ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Steiner Transitive-Closure Spanners of Low-Dimensional Posets ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Property testing lower bounds via communication complexity ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Transitive-Closure Spanners: A Survey ⋮ Local Property Reconstruction and Monotonicity ⋮ Unnamed Item ⋮ Limitations of Local Filters of Lipschitz and Monotone Functions ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Lasserre integrality gaps for graph spanners and related problems

This page was built for publication: Transitive-Closure Spanners