Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
From MaRDI portal
Publication:6202221
DOI10.1145/3583668.3594604arXiv2304.04699OpenAlexW4380880028MaRDI QIDQ6202221
Publication date: 26 March 2024
Published in: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2304.04699
Cites Work
- Unnamed Item
- Unnamed Item
- Distributed minimum dominating set approximations in restricted families of graphs
- Graph minors. XX: Wagner's conjecture
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Low diameter graph decompositions
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- The extremal function for complete minors
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Property testing of planarity in the \textsf{CONGEST} model
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Deterministic coin tossing with applications to optimal parallel list ranking
- Locality in Distributed Graph Algorithms
- Tight Analyses of Two Local Load Balancing Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Distributed Dominating Set Approximations beyond Planar Graphs
- On the complexity of local distributed graph problems
- Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
- Near-optimal Distributed Triangle Enumeration via Expander Decompositions
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- The Power of Distributed Verifiers in Interactive Proofs
- Round- and Message-Optimal Distributed Graph Algorithms
- Minor Excluded Network Families Admit Fast Distributed Algorithms
- Planar diameter via metric compression
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Excluded minors, network decomposition, and multicommodity flow
- Distributed Algorithms for Planar Networks I
- Distributed Strong Diameter Network Decomposition
- A Local Constant Factor MDS Approximation for Bounded Genus Graphs
- Low-Congestion Shortcuts without Embedding
- Distributed MST and Routing in Almost Mixing Time
- Distributed Computing
- Distributed Almost Exact Approximations for Minor-Closed Families
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
