Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut

DOI10.1137/1.9781611974331.ch16zbMath1410.68383OpenAlexW4254419859MaRDI QIDQ4575592

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

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (17)

Property testing of planarity in the \textsf{CONGEST} model ⋮ Low-congestion shortcuts without embedding ⋮ Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Minimum cost flow in the CONGEST model ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Sparse Semi-Oblivious Routing: Few Random Paths Suffice ⋮ Low-congestion shortcut and graph parameters ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Compact distributed certification of planar graphs ⋮ Local certification of graphs with bounded genus

This page was built for publication: Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut