Can we locally compute sparse connected subgraphs?

DOI10.1007/978-3-319-58747-9_6zbMath1489.68241OpenAlexW2611251582MaRDI QIDQ2399362

Publication date: 22 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-58747-9_6

Graph theory (including graph drawing) in computer science (68R10) Computational aspects of data analysis and big data (68T09)

Related Items (1)

Unnamed Item

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Local computation algorithms for graphs of non-constant degrees
Distributed approximation of capacitated dominating sets
A simple storage scheme for strings achieving entropy bounds
Property-preserving data reconstruction
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Non-local probes do not help with many graph problems
Best of two local models: centralized local and distributed local algorithms
The hardness of approximating spanner problems
Improved low-degree testing and its applications
Learning Polynomials with Queries: The Highly Noisy Case
Noise Tolerance of Expanders and Sublinear Expansion Reconstruction
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
Converting Online Algorithms to Local Computation Algorithms
A Local Computation Approximation Scheme to Maximum Matching
Local Reconstructors and Tolerant Testers for Connectivity and Diameter
Local list-decoding and testing of random linear codes from high error
A log-star distributed maximal independent set algorithm for growth-bounded graphs
Local Algorithms for Sparse Spanning Graphs
Constructing near spanning trees with few local inspections
Local Computation of PageRank Contributions
Random-Self-Reducibility of Complete Sets
The Locality of Distributed Symmetry Breaking
On the efficiency of local decoding procedures for error-correcting codes
Bookmark-Coloring Algorithm for Personalized PageRank Computing
Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
The price of being near-sighted
Squeezing succinct data structures into entropy bounds
Distance Approximation in Bounded-Degree and General Sparse Graphs
Keeping Mobile Robot Swarms Connected
An Improved Distributed Algorithm for Maximal Independent Set
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
An Optimal Synchronizer for the Hypercube
What Can be Computed Locally?
Local Graph Partitions for Approximation and Testing
Distributed (δ+1)-coloring in linear (in δ) time
An improved constant-time approximation algorithm for maximum~matchings
Finding sparse cuts locally using evolving sets
A new technique for distributed symmetry breaking
Deterministic distributed vertex coloring in polylogarithmic time
On the complexity of distributed graph coloring
Statistical Encoding of Succinct Data Structures
Approximating the Minimum Spanning Tree Weight in Sublinear Time
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
Local Monotonicity Reconstruction
Distributed Computing
Algorithms – ESA 2005
Local Distributed Decision
What cannot be computed locally!
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
Limitations of Local Filters of Lipschitz and Monotone Functions
Distributed algorithms for ultrasparse spanners and linear size skeletons
Pseudorandom generators without the XOR lemma

This page was built for publication: Can we locally compute sparse connected subgraphs?