# Single source shortest paths in $H$-minor free graphs

Preprint · Raphael Yuster

- Archive id: arxiv:0809.2970
- Published: 2008-09-17
- arXiv: https://arxiv.org/abs/0809.2970
- Citations: 0
- Source URL: https://arxiv.org/abs/0809.2970
- PDF: https://arxiv.org/pdf/0809.2970
- Provenance: arxiv

## Abstract

We present an algorithm for the Single Source Shortest Paths (SSSP) problem in \\emph{$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 $\\tilde{O}(n^{\\sqrt{11.5}-2} \\log L) \\le 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.