Distributed planar reachability in nearly optimal time
type: Item
instance of: scholarly article
title: Distributed planar reachability in nearly optimal time
zbMATH Open document ID: 1540.68196
author: M. Parter
publication date: 2023-11-02T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 7760527
zbMATH Keywords: distributed graph algorithms
zbMATH Keywords: planar graphs
zbMATH Keywords: reachability
MaRDI profile type: Publication
cites work: New hardness results for planar graph problems in p and an algorithm for sparsest cut
cites work: Q4607916
cites work: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
cites work: Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
cites work: Reachability and shortest paths in the broadcast CONGEST model
cites work: Distributed verification and hardness of distributed approximation
cites work: Distributed exact shortest paths in sublinear time
cites work: Planar graphs, negative weight edges, shortest paths, and near linear time
cites work: A distributed algorithm for directed minimum-weight spanning tree
cites work: Distance labeling in graphs (extended abstract)
cites work: Distributed Algorithms for Planar Networks I
cites work: Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
cites work: Improved distributed algorithms for exact shortest paths
cites work: Near-optimal distributed DFS in planar graphs
cites work: Round- and Message-Optimal Distributed Graph Algorithms
cites work: Low-Congestion Shortcuts without Embedding
cites work: Near-optimal low-congestion shortcuts on bounded parameter graphs
cites work: Minor Excluded Network Families Admit Fast Distributed Algorithms
cites work: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
cites work: A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
cites work: Improved algorithms for min cut and max flow in undirected planar graphs
cites work: A Randomized Parallel Algorithm for Single-Source Shortest Paths
cites work: Fast partial distance estimation and applications
cites work: Planar diameter via metric compression
cites work: A Separator Theorem for Planar Graphs
cites work: Q5743390
cites work: Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
cites work: Distributed approximation algorithms for weighted shortest paths
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Distributed Verification and Hardness of Distributed Approximation
cites work: Compact oracles for reachability and approximate distances in planar digraphs
DOI: 10.4230/LIPICS.DISC.2020.38
description: scientific article; zbMATH DE number 7760527