APSP on Sparse Undirected Unweighted Graphs: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


n: number of vertices
$n$: number of vertices


m: number of edges
$m$: number of edges


== Table of Algorithms ==  
== Table of Algorithms ==  


Currently no algorithms in our database for the given problem.
{| class="wikitable sortable"  style="text-align:center;" width="100%"


== Time Complexity graph ==
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference


[[File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Time.png|1000px]]
|-


== Space Complexity graph ==
| [[Seidel's algorithm (APSP on Dense Undirected Unweighted Graphs; APSP on Sparse Undirected Unweighted Graphs All-Pairs Shortest Paths (APSP))|Seidel's algorithm]] || 1995 || $O (n^{2.{37}3} \log n)$ || $O(n^{2})$ || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0022000085710781 Time]
|-
|}


[[File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Space.png|1000px]]
== Time Complexity Graph ==


== Pareto Decades graph ==
[[File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Time.png|1000px]]
 
[[File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Pareto Frontier.png|1000px]]

Latest revision as of 09:07, 28 April 2023

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

Error creating thumbnail: Unable to save thumbnail to destination
Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=APSP_on_Sparse_Undirected_Unweighted_Graphs&oldid=47667"