Shortest distances as enumeration problem

DOI10.1016/j.dam.2023.08.027arXiv2005.06827OpenAlexW3024153740MaRDI QIDQ6184314

Markus L. Schmid, Stefan Neubert, Tobias Friedrich, Katrin Casel

Publication date: 24 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.06827

zbMATH Keywords

enumerationshortest pathsfine-grained complexityAPSP

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• On generating all maximal independent sets
• On the exponent of all pairs shortest path problem
• An improved combinatorial algorithm for Boolean matrix multiplication
• A new approach to all-pairs shortest paths on real-weighted graphs
• Linear-time in-place DFS and BFS on the word RAM
• Undirected single-source shortest paths with positive integer weights in linear time
• All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Strict fibonacci heaps
• A Theorem on Boolean Matrices
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Fine-Grained Complexity of Regular Path Queries

This page was built for publication: Shortest distances as enumeration problem