Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
DOI10.1137/1.9781611974331.CH16zbMATH Open1410.68383OpenAlexW4254419859MaRDI QIDQ4575592FDOQ4575592
Authors: Mohsen Ghaffari, Bernhard Haeupler 
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch16
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distributed algorithms (68W15)
Cited In (24)
- Title not available (Why is that?)
- Local certification of graphs with bounded genus
- Low-congestion shortcut and graph parameters
- Low-congestion shortcut and graph parameters
- Minimum cost flow in the CONGEST model
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Minor excluded network families admit fast distributed algorithms
- Near-optimal distributed computation of small vertex cuts
- Faster distributed shortest path approximations via shortcuts
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- Low-congestion shortcuts without embedding
- Distributed algorithms for planar networks. I: Planar embedding
- Compact distributed certification of planar graphs
- Low-congestion shortcuts without embedding
- Property testing of planarity in the \textsf{CONGEST} model
- Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Sparse Semi-Oblivious Routing: Few Random Paths Suffice
- Distributed planar reachability in nearly optimal time
- A distributed algorithm for directed minimum-weight spanning tree
- Distributed MST and broadcast with fewer messages, and faster gossiping
This page was built for publication: Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575592)
