Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs (Q4993322): Difference between revisions

@@ label / en / label / en @@
+Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
@@ Property / DOI @@
-.4230/LIPIcs.ITCS.2018.52
@@ Property / DOI: 10.4230/LIPIcs.ITCS.2018.52 / rank @@
-Normal rank
@@ Property / arXiv ID @@
+.02084
@@ Property / arXiv ID: 2105.02084 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743464
@@ Property / cites work: Q5743464 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234097
@@ Property / cites work: Q4234097 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
+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 @@
+Fully Dynamic Maximal Matching in O (log n) Update Time
+Normal rank
@@ Property / cites work @@
+Q4228453
@@ Property / cites work: Q4228453 / rank @@
+Normal rank
@@ Property / cites work @@
+Fully Dynamic Matching in Bipartite Graphs
@@ Property / cites work: Fully Dynamic Matching in Bipartite Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Faster Fully Dynamic Matchings with Small Approximation Ratios
+Normal rank
@@ Property / cites work @@
+Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
+Normal rank
@@ Property / cites work @@
+New deterministic approximation algorithms for fully dynamic matching
+Normal rank
@@ Property / cites work @@
+Shortest augmenting paths for online matchings on trees
+Normal rank
@@ Property / cites work @@
+Optimal Dynamic Distributed MIS
@@ Property / cites work: Optimal Dynamic Distributed MIS / rank @@
+Normal rank
@@ Property / cites work @@
+Compact routing schemes with improved stretch
@@ Property / cites work: Compact routing schemes with improved stretch / rank @@
+Normal rank
@@ Property / cites work @@
+Q2969610
@@ Property / cites work: Q2969610 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
+Normal rank
@@ Property / cites work @@
+A Fast Algorithm for Constructing Sparse Euclidean Spanners
+Normal rank
@@ Property / cites work @@
+Optimal euclidean spanners
@@ Property / cites work: Optimal euclidean spanners / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
+Normal rank
@@ Property / cites work @@
+Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
+Normal rank
@@ Property / cites work @@
+Characterizing multiterminal flow networks and computing flows in networks of small treewidth
+Normal rank
@@ Property / cites work @@
+Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
+Normal rank
@@ Property / cites work @@
+Efficient bounds for the stable set, vertex cover and set packing problems
+Normal rank
@@ Property / cites work @@
+An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
+Normal rank
@@ Property / cites work @@
+Extensions and limits to vertex sparsification
@@ Property / cites work: Extensions and limits to vertex sparsification / rank @@
+Normal rank
@@ Property / cites work @@
+Local computation algorithms for graphs of non-constant degrees
+Normal rank
@@ Property / cites work @@
+A Local Computation Approximation Scheme to Maximum Matching
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
+Normal rank
@@ Property / cites work @@
+Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
+Normal rank
@@ Property / cites work @@
+Maintaining a large matching and a small vertex cover
+Normal rank
@@ Property / cites work @@
+Local-on-Average Distributed Tasks
@@ Property / cites work: Local-on-Average Distributed Tasks / rank @@
+Normal rank
@@ Property / cites work @@
+Distributed Computing: A Locality-Sensitive Approach
+Normal rank
@@ Property / cites work @@
+Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
+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 @@
+Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
+Normal rank
@@ Property / OpenAlex ID @@
+W2782624220
@@ Property / OpenAlex ID: W2782624220 / rank @@
+Normal rank
@@ Property / title @@
+Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs (English)
+Normal rank
@@ Property / DOI @@
+.4230/LIPICS.ITCS.2018.52
@@ Property / DOI: 10.4230/LIPICS.ITCS.2018.52 / rank @@
+Normal rank