scientific article; zbMATH DE number 7053343

zbMath1421.68127MaRDI QIDQ5743466

Stephan Holzer, Roger Wattenhofer, Silvio Frischknecht

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095207

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (18)

Low-congestion shortcuts without embedding ⋮ Distributed Testing of Distance-k Colorings ⋮ Distributed distance computation and routing with small messages ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ A note on hardness of diameter approximation ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Algebraic methods in the congested clique ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Unnamed Item ⋮ Message lower bounds via efficient network synchronization ⋮ Distributed Spanner Approximation ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

Cites Work

• Unnamed Item
• Unnamed Item
• Tight bounds for distributed minimum-weight spanning tree verification
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• On the exponent of all pairs shortest path problem
• A new approach to all-pairs shortest paths on real-weighted graphs
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• A tight unconditional lower bound on distributed randomwalk computation
• Undirected single-source shortest paths with positive integer weights in linear time
• A New Combinatorial Approach for Sparse Graph Problems
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• The price of being near-sighted
• Information Bounds Are Weak in the Shortest Distance Problem
• Locality in Distributed Graph Algorithms
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Communication Complexity
• Hundreds of impossibility results for distributed computing
• On the locality of bounded growth
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Distributed verification and hardness of distributed approximation
• Distributed MST for constant diameter graphs

This page was built for publication: