Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut

DOI10.1137/1.9781611974331.CH16MaRDI QIDQ4575592zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Low-congestion shortcuts without embedding
• Low-congestion shortcuts without embedding
• Low-congestion shortcut and graph parameters
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• Low-congestion shortcut and graph parameters

Cited in

(24)

• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• 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
• Faster distributed shortest path approximations via shortcuts
• Near-optimal distributed computation of small vertex cuts
• 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
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• 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)