Image de couverture de livre

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Karczmarz, Adam, Nadara, Wojciech, Sokołowski, Marek
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
par: Holm, Jacob, et autres
Publié: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
par: Górkiewicz, Adam, et autres
Publié: (2025)

Fully Dynamic Strongly Connected Components in Planar Digraphs
par: Karczmarz, Adam, et autres
Publié: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
par: Ashvinkumar, Vikrant, et autres
Publié: (2024)

Fully Dynamic Shortest Paths in Sparse Digraphs
par: Karczmarz, Adam, et autres
Publié: (2024)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
par: Karczmarz, Adam, et autres
Publié: (2024)

Algorithm Engineering of SSSP With Negative Edge Weights
par: Cassis, Alejandro, et autres
Publié: (2025)

Fast decremental tree sums in forests
par: Berendsohn, Benjamin Aram, et autres
Publié: (2026)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
par: Kluk, Kacper, et autres
Publié: (2026)

Fully Dynamic Algorithms for Transitive Reduction
par: Goranci, Gramoz, et autres
Publié: (2025)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
par: Jaffke, Lars, et autres
Publié: (2025)

A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding
par: Li, Jason, et autres
Publié: (2024)

High Probability Work Efficient Parallel Algorithms
par: Hutton, Chase, et autres
Publié: (2026)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
par: Jiang, Yonggang, et autres
Publié: (2025)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Dynamic data structures for twin-ordered matrices
par: Bosek, Bartłomiej, et autres
Publié: (2026)

Beyond a Single Queue: Multi-Level-Multi-Queue as an Effective Design for SSSP problems on GPUs
par: Hu, Zhengding, et autres
Publié: (2026)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
par: Korhonen, Tuukka, et autres
Publié: (2024)

Dynamic Detours
par: Dadush, Daniel, et autres
Publié: (2026)

Treedepth Inapproximability and Exponential ETH Lower Bound
par: Bonnet, Édouard, et autres
Publié: (2025)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
par: Haeupler, Bernhard, et autres
Publié: (2025)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
par: Brand, Jan van den, et autres
Publié: (2025)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
par: Oum, Sang-il, et autres
Publié: (2026)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
par: Ashvinkumar, Vikrant, et autres
Publié: (2026)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
par: Bourneuf, Romain, et autres
Publié: (2025)

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
par: Dadush, Daniel, et autres
Publié: (2025)

Scheduling Jobs with Work-Inefficient Parallel Solutions
par: Kuszmaul, William, et autres
Publié: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
par: Mitrović, Slobodan, et autres
Publié: (2025)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
par: Ghaffari, Mohsen, et autres
Publié: (2024)

Circuit Diameter of Polyhedra is Strongly Polynomial
par: Natura, Bento
Publié: (2026)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
par: Majewski, Konrad, et autres
Publié: (2021)

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
par: Cenciarelli, Pietro, et autres
Publié: (2016)

Improved Time-Space Tradeoffs for 3SUM-Indexing
par: Dinur, Itai, et autres
Publié: (2025)

Strongly Polynomial Frame Scaling to High Precision
par: Dadush, Daniel, et autres
Publié: (2024)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
par: Bérczi, Kristóf, et autres
Publié: (2024)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
par: Koh, Zhuan Khye, et autres
Publié: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
par: Dory, Michal, et autres
Publié: (2022)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
par: Woodruff, David P., et autres
Publié: (2024)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
par: Amir, Amihood, et autres
Publié: (2026)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
par: Chen, Kuowen, et autres
Publié: (2025)