Can we locally compute sparse connected subgraphs?
From MaRDI portal
Publication:2399362
DOI10.1007/978-3-319-58747-9_6zbMATH Open1489.68241OpenAlexW2611251582MaRDI QIDQ2399362FDOQ2399362
Authors: Ronitt Rubinfeld 
Publication date: 22 August 2017
Full work available at URL: https://doi.org/10.1007/978-3-319-58747-9_6
Recommendations
Computational aspects of data analysis and big data (68T09) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Testing and reconstruction of Lipschitz functions with applications to data privacy
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- An Optimal Synchronizer for the Hypercube
- A simple storage scheme for strings achieving entropy bounds
- A new technique for distributed symmetry breaking
- What cannot be computed locally!
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pseudorandom generators without the XOR lemma
- The hardness of approximating spanner problems
- Random-Self-Reducibility of Complete Sets
- On the complexity of distributed graph coloring
- Distributed Computing
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time
- Distributed approximation of capacitated dominating sets
- Local Distributed Decision
- Title not available (Why is that?)
- Squeezing succinct data structures into entropy bounds
- Deterministic distributed vertex coloring in polylogarithmic time
- Learning polynomials with queries: The highly noisy case
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Local monotonicity reconstruction
- Lower bounds for local monotonicity reconstruction from transitive-closure spanners
- Property-preserving data reconstruction
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- On the efficiency of local decoding procedures for error-correcting codes
- Title not available (Why is that?)
- Improved low-degree testing and its applications
- Statistical Encoding of Succinct Data Structures
- Local list-decoding and testing of random linear codes from high error
- Local Graph Partitions for Approximation and Testing
- The locality of distributed symmetry breaking
- The price of being near-sighted
- Noise tolerance of expanders and sublinear expansion reconstruction
- Converting online algorithms to local computation algorithms
- A Local Computation Approximation Scheme to Maximum Matching
- Local reconstructors and tolerant testers for connectivity and diameter
- Keeping Mobile Robot Swarms Connected
- Local computation algorithms for graphs of non-constant degrees
- Algorithms – ESA 2005
- What Can be Computed Locally?
- An Improved Distributed Algorithm for Maximal Independent Set
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Finding sparse cuts locally using evolving sets
- Best of two local models: centralized local and distributed local algorithms
- Distance Approximation in Bounded-Degree and General Sparse Graphs
- Non-local probes do not help with many graph problems
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Bookmark-Coloring Algorithm for Personalized PageRank Computing
- Distributed algorithms for ultrasparse spanners and linear size skeletons
- Local algorithms for sparse spanning graphs
- Constructing near spanning trees with few local inspections
- Local Computation of PageRank Contributions
- A local algorithm for constructing spanners in minor-free graphs
- Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
- Limitations of local filters of Lipschitz and monotone functions
Cited In (1)
This page was built for publication: Can we locally compute sparse connected subgraphs?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399362)
