APSP on Sparse Undirected Unweighted Graphs (All-Pairs Shortest Paths (APSP))

Description

In this case, the graph $G=(V,E)$ that we consider is sparse ($m = O(n)$), is undirected, and is unweighted (or equivalently, has all unit weights).

Related Problems

Generalizations: APSP

Related: APSP on Dense Directed Graphs with Arbitrary Weights, APSP on Dense Undirected Graphs with Arbitrary Weights, APSP on Geometrically Weighted Graphs, APSP on Dense Undirected Graphs with Positive Integer Weights, APSP on Sparse Directed Graphs with Arbitrary Weights, APSP on Sparse Undirected Graphs with Positive Integer Weights, APSP on Sparse Undirected Graphs with Arbitrary Weights, APSP on Dense Directed Unweighted Graphs, APSP on Dense Undirected Unweighted Graphs, APSP on Sparse Directed Unweighted Graphs, (5/3)-approximate ap-shortest paths

Parameters

$n$: number of vertices

$m$: number of edges

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Seidel's algorithm	1995	$O (n^{2.{37}3} \log n)$	$O(n^{2})$	Exact	Deterministic	Time

Time Complexity Graph