A note on hardness of diameter approximation

DOI10.1016/J.IPL.2017.12.010zbMath1427.68106arXiv1705.02127OpenAlexW2613923799MaRDI QIDQ1705693

Sebastian Krinninger, Karl Bringmann

Publication date: 16 March 2018

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsgraph algorithmsdistributed computinghardness in P

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• On the distributional complexity of disjointness
• Which problems have strongly exponential complexity?
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Distributed Computing: A Locality-Sensitive Approach
• New Bounds for Approximating Extremal Distances in Undirected Graphs
• Communication Complexity
• Better Approximation Algorithms for the Graph Diameter
• Fast approximation algorithms for the diameter and radius of sparse graphs

This page was built for publication: A note on hardness of diameter approximation