Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners

DOI10.1007/978-3-642-15369-3_34zbMath1305.68090OpenAlexW1632764828MaRDI QIDQ5901180

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

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10203/24883

zbMATH Keywords

hypercubemonotone functionsspannersproperty testinghypergridproperty reconstruction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)

Related Items

Improved Approximation for the Directed Spanner Problem ⋮ Steiner Transitive-Closure Spanners of Low-Dimensional Posets ⋮ Transitive-Closure Spanners: A Survey