Planar diameter via metric compression

DOI10.1145/3313276.3316358zbMath1433.68301arXiv1912.11491OpenAlexW2951760736MaRDI QIDQ5212756

Jason Li, Merav Parter

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathdiameterplanar graphsdistributed computingmetric compression

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (7)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ 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 ⋮ Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs ⋮ Low-congestion shortcut and graph parameters ⋮ Packing and covering balls in graphs excluding a minor

This page was built for publication: Planar diameter via metric compression