Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

Cites work

(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
A fast and simple randomized parallel algorithm for maximal matching
A fast and simple randomized parallel algorithm for the maximal independent set problem
A local constant factor MDS approximation for bounded genus graphs
A Separator Theorem for Planar Graphs
A separator theorem in minor-closed classes
A Simple Parallel Algorithm for the Maximal Independent Set Problem
A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
A sublinear bipartiteness tester for bounded degree graphs
Algorithms - ESA 2003
Approximating the Permanent
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Best of two local models: centralized local and distributed local algorithms
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Clustering with qualitative information
Complete Minors in Graphs Without Sparse Cuts
Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
Correlation clustering
Correlation clustering, maximizing agreements via semidefinite programming
Deterministic distributed edge-coloring via hypergraph maximal matching
Deterministic distributed edge-coloring with fewer colors
Deterministic Edge Connectivity in Near-Linear Time
Deterministic expander routing: faster and more versatile
Diameter and treewidth in minor-closed graph families
Distributed algorithms for planar networks. I: Planar embedding
Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
Distributed algorithms for weighted problems in sparse graphs
Distributed Almost Exact Approximations for Minor-Closed Families
Distributed approximate matching
Distributed approximate maximum matching in the CONGEST model
Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
Distributed Approximation Algorithms for Planar Graphs
Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
Distributed approximation of maximum independent set and maximum matching
Distributed Dominating Set Approximations beyond Planar Graphs
Distributed edge connectivity in sublinear time
Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
Distributed minimum dominating set approximations in restricted families of graphs
Distributed MST and routing in almost mixing time
Distributed planar reachability in nearly optimal time
Distributed subgraph finding: progress and challenges (invited talk)
Distributed Weighted Matching
Dynamic minimum spanning forest with subpolynomial worst-case update time
Edge separators for graphs of bounded genus with applications
Edge Separators of Planar and Outerplanar Graphs With Applications
Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
Equivalence of local treewidth and linear local treewidth and its algorithmic applications
Excluded minors, network decomposition, and multicommodity flow
Fast distributed algorithms for testing graph properties
Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
Fast Distributed Approximations in Planar Graphs
Faster distributed shortest path approximations via shortcuts
Finding forbidden minors in sublinear time: a \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
Finding small simple cycle separators for 2-connected planar graphs
Graph Clustering using Effective Resistance
Graph expansion and the unique games conjecture
Graph minors. II. Algorithmic aspects of tree-width
Graph minors. XVI: Excluding a non-planar graph
Graph minors. XX: Wagner's conjecture
Hardness of Distributed Optimization
scientific article; zbMATH DE number 7561283 (Why is no real title available?)
scientific article; zbMATH DE number 7650908 (Why is no real title available?)
scientific article; zbMATH DE number 7774264 (Why is no real title available?)
scientific article; zbMATH DE number 7788509 (Why is no real title available?)
scientific article; zbMATH DE number 7788511 (Why is no real title available?)
Improved Distributed Approximate Matching
Improved distributed approximations for maximum independent set
Linear-time approximation for maximum weight matching
Local tree-width, excluded minors, and approximation algorithms
Low diameter graph decompositions
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
Low-congestion shortcuts without embedding
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
Maximum matching and a polyhedron with 0,1-vertices
Minor excluded network families admit fast distributed algorithms
Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions
Near-optimal distributed DFS in planar graphs
Near-optimal Distributed Triangle Enumeration via Expander Decompositions
Near-optimal low-congestion shortcuts on bounded parameter graphs
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
On clusterings: good, bad and spectral
On derandomizing local distributed algorithms
On Distributed Listing of Cliques
On the complexity of local distributed graph problems
On the distributed complexity of computing maximal matchings
Planar diameter via metric compression
Polylogarithmic-time deterministic network decomposition and distributed derandomization
Property testing of planarity in the \textsf{CONGEST} model
Round- and message-optimal distributed graph algorithms
Some recent progress and applications in graph minor theory
Subexponential algorithms for unique games and related problems
Sublinear-time distributed algorithms for detecting small cliques and even cycles
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
The extremal function for complete minors
The locality of distributed symmetry breaking
The power of distributed verifiers in interactive proofs

This page was built for publication: Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241986)