Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
From MaRDI portal
Publication:4993322
DOI10.4230/LIPIcs.ITCS.2018.52zbMath1462.68147arXiv2105.02084OpenAlexW2782624220MaRDI QIDQ4993322
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/2105.02084
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Related Items
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Improved Dynamic Graph Coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local computation algorithms for graphs of non-constant degrees
- Efficient bounds for the stable set, vertex cover and set packing problems
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Shortest augmenting paths for online matchings on trees
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A Local Computation Approximation Scheme to Maximum Matching
- Extensions and limits to vertex sparsification
- Maintaining a large matching and a small vertex cover
- Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
- Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- The Locality of Distributed Symmetry Breaking
- Fully Dynamic Matching in Bipartite Graphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- Distributed Computing: A Locality-Sensitive Approach
- Local-on-Average Distributed Tasks
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
- An Optimal Synchronizer for the Hypercube
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Compact routing schemes with improved stretch
- New deterministic approximation algorithms for fully dynamic matching
- A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
- Optimal Dynamic Distributed MIS
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- Fully Dynamic Maximal Matching in O (log n) Update Time
- Optimal euclidean spanners
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
