Can we locally compute sparse connected subgraphs? (Q2399362): Difference between revisions

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