Single source shortest paths in H-minor free graphs

2008/09/17 by Raphael Yuster, Yuster, Raphael
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.0809.2970

openalex publication_date 2008/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm for the Single Source Shortest Paths (SSSP) problem in H-minor free graphs. For every fixed H, if G is a graph with n vertices having integer edge lengths and s is a designated source vertex of G, the algorithm runs in O(n^√(11.5)-2 log L) ≤ O(n^1.392 log L) time, where L is the absolute value of the smallest edge length. The algorithm computes shortest paths and the distances from s to all vertices of the graph, or else provides a certificate that G is not H-minor free. Our result improves an earlier O(n^1.5 log L) time algorithm for this problem, which follows from a general SSSP algorithm of Goldberg.

Citations

• A note on two problems in connexion with graphs

Related

• Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights
• Shortest Path Algorithms between Theory and Practice
• A Faster Directed Single-Source Shortest Path Algorithm
• Single-Source Shortest Paths with Negative Real Weights in O(mn^8/9) Time
• Negative-Weight Single-Source Shortest Paths in Near-linear Time