APSP on Geometrically Weighted Graphs

In this case, the graph $G=(V,E)$ that we consider may be dense or sparse, may be directed or undirected, and has weights from a fixed set of $c$ values.

Parameters

$n$ : number of vertices
$m$ : number of edges
$c$ : number of unique weights

Related Problems

APSP11
- APSP on Dense Directed Graphs with Arbitrary Weights
- APSP on Dense Undirected Graphs with Arbitrary Weights
- APSP on Geometrically Weighted Graphs
- APSP on Sparse Directed Graphs with Arbitrary 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
- APSP on Sparse Undirected Unweighted Graphs
- (5/3)-approximate ap-shortest paths
- APSP on Directed Graphs with Real-Valued Weights

APSP on Dense Undirected Graphs with Positive Integer Weights

APSP on Sparse Undirected Graphs with Positive Integer Weights

Approximate Distance Oracle

Directed, Weighted APSP

Undirected, Weighted APSP

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
Chan (Geometrically Weighted)	2009	$O(n^{2.844})$	$O(l n^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table