Minor Excluded Network Families Admit Fast Distributed Algorithms

DOI10.1145/3212734.3212776zbMath1428.68382arXiv1801.06237OpenAlexW2962991864MaRDI QIDQ5197712

Bernhard Haeupler, Jason Li, Goran Zuzic

Publication date: 19 September 2019

Published in: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.06237

zbMATH Keywords

shortcutsdistributed computingCongestlow-congestion shortcutsgraph structure theoremminor excluded graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (6)

Property testing of planarity in the \textsf{CONGEST} model ⋮ Low-congestion shortcuts without embedding ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Low-congestion shortcut and graph parameters

This page was built for publication: Minor Excluded Network Families Admit Fast Distributed Algorithms