Exact Shortest Paths and Maximum Flow in Planar Networks in the CONGEST Model
cs.DC
Submitted: 2026-11-01
Updated: 2026-11-01
Code: https://github.com/ssenge/ExactShortestPathsAndFlowsOnPlanarGraphs
Terminology
Sources
- Planar Embedding of Okamura-Seymour Quasimetrics in Polynomial Time with an Application to Distributed SSSP
- Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
- Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
- Minimum Cost Flow in the CONGEST Model
- Planar Diameter via Metric Compression
- Distributed Maximum Flow in Planar Graphs
- Deterministic Distributed DFS and Other Problems via Cycle Separators in Planar Graphs
- A Simple Distributed Deterministic Planar Separator
- $\tilde{\text{O}}$ptimal Distributed Maximum Flow Approximation in Undirected Planar Graphs
Related papers
- Programmable Probabilistic Computer with 1,000,000 p-bits
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends