Local computation algorithms for spanners

DOI10.4230/LIPICS.ITCS.2019.58MaRDI QIDQ5090437zbMATH OpenFDO

Authors Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee, M. Parter

Publication date 18 July 2022

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

zbMATH Keywords

graph spannerslocal computation algorithmssub-linear algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Local Computation of Nearly Additive Spanners
• Local computation algorithms for graphs of non-constant degrees
• On the probe complexity of local computation algorithms
• Local algorithms for sparse spanning graphs
• Local algorithms for sparse spanning graphs

Cites work

• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• A Brief Introduction to Property Testing
• A Local Computation Approximation Scheme to Maximum Matching
• A local algorithm for constructing spanners in minor-free graphs
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• An Optimal Synchronizer for the Hypercube
• Constant-Time Local Computation Algorithms
• Constructing near spanning trees with few local inspections
• Converting online algorithms to local computation algorithms
• Derandomizing local distributed algorithms under bandwidth restrictions
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Deterministic stateless centralized local algorithms for bounded degree graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Efficient algorithms for constructing very sparse spanners and emulators
• Fast deterministic distributed algorithms for sparse spanners
• Fully dynamic randomized algorithms for graph spanners
• Fully dynamic spanners with worst-case update time
• Graph spanners
• Local Computation of Nearly Additive Spanners
• Local algorithms for sparse spanning graphs
• Local computation algorithms for graphs of non-constant degrees
• New techniques and tighter bounds for local computation algorithms
• On some extremal problems in graph theory
• On the locality of distributed sparse spanner construction
• Property testing and its connection to learning and approximation
• Routing with Polynomial Communication-Space Trade-Off
• Space-efficient local computation algorithms
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Spectral sparsification via random spanners
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(10)

• Local MST computation with short advice
• Constant-Time Local Computation Algorithms
• Average Sensitivity of Graph Algorithms
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Improved Local Computation Algorithm for Set Cover via Sparsification
• Locally computing edge orientations
• Spanning adjacency oracles in sublinear time
• Local algorithms for sparse spanning graphs
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• Light spanners for high dimensional norms via stochastic decompositions

This page was built for publication: Local computation algorithms for spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090437)