Image de couverture de livre

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Saha, Barna, Williams, Virginia Vassilevska, Xu, Yinzhan, Ye, Christopher
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Computational Complexity F.2.2; F.1.3
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

An Algorithm for a Variation of the Shortest Common Superstring Problem
par: Gilfanov, Arthur
Publié: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
par: Salas, Jesus
Publié: (2025)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
par: Kowaluk, Miroslaw, et autres
Publié: (2025)

A Faster Directed Single-Source Shortest Path Algorithm
par: Duan, Ran, et autres
Publié: (2026)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
par: Duan, Ran, et autres
Publié: (2025)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
par: Goldenberg, Elazar, et autres
Publié: (2022)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

Spanning Trees Minimizing Branching Costs
par: Gargano, Luisa, et autres
Publié: (2024)

Towards universally optimal sorting algorithms
par: Sen, Sandeep
Publié: (2025)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
par: Sarriguren, Alfredo Goñi
Publié: (2024)

Graph Threading with Turn Costs
par: Demaine, Erik D., et autres
Publié: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
par: Clinch, Katie, et autres
Publié: (2024)

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
par: de Berg, Mark, et autres
Publié: (2026)

Line Cover and Related Problems
par: Bentert, Matthias, et autres
Publié: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
par: Lingas, Andrzej
Publié: (2026)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

Revisiting Path Contraction and Cycle Contraction
par: Krithika, R., et autres
Publié: (2024)

Approximately Partitioning Vertices into Short Paths
par: Gong, Mingyang, et autres
Publié: (2026)

On the Approximability of Unsplittable Flow on a Path with Time Windows
par: Armbruster, Alexander, et autres
Publié: (2025)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
par: Balzotti, Lorenzo
Publié: (2020)

Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
par: Lindermayr, Alexander, et autres
Publié: (2025)

Connected Components in Linear Work and Near-Optimal Time
par: Farhadi, Alireza, et autres
Publié: (2023)

SimdQuickHeap: The QuickHeap Reconsidered
par: Breitling, Johannes, et autres
Publié: (2026)

Multiplication of 0-1 matrices via clustering
par: Jansson, Jesper, et autres
Publié: (2025)

Fast approximate $\ell$-center clustering in high dimensional spaces
par: Kowaluk, Mirosław, et autres
Publié: (2025)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
par: Mosenzon, Ron
Publié: (2025)

On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
par: Goswami, Mayank, et autres
Publié: (2022)

Fast and Simple Sorting Using Partial Information
par: Haeupler, Bernhard, et autres
Publié: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

More Asymmetry Yields Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2024)

Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams
par: Chakrabarti, Amit, et autres
Publié: (2024)

All-Hops Shortest Paths
par: Williams, Virginia Vassilevska, et autres
Publié: (2024)

Large cliques and large independent sets: can they coexist?
par: Feige, Uriel, et autres
Publié: (2025)

Minimum Riesz s-Energy Subset Selection in Ordered Point Sets via Dynamic Programming
par: Emmerich, Michael
Publié: (2025)

New Sorting Algorithm Wave Sort (W-Sort)
par: Wei, Jia Xu
Publié: (2025)