V - the graph vertex typeE - the graph edge typepublic class GreedyMultiplicativeSpanner<V,E> extends Object implements SpannerAlgorithm<E>
The spanner is guaranteed to contain O(n^{1+1/k}) edges and the shortest path distance between any two vertices in the spanner is at most 2k-1 times the corresponding shortest path distance in the original graph. Here n denotes the number of vertices of the graph.
The algorithm is described in: Althoefer, Das, Dobkin, Joseph, Soares. On Sparse Spanners of Weighted Graphs. Discrete Computational Geometry 9(1):81-100, 1993.
If the graph is unweighted the algorithm runs in O(m n^{1+1/k}) time. Setting k to infinity will result in a slow version of Kruskal's algorithm where cycle detection is performed by a BFS computation. In such a case use the implementation of Kruskal with union-find. Here n and m are the number of vertices and edges of the graph respectively.
If the graph is weighted the algorithm runs in O(m (n^{1+1/k} + nlogn)) time by using Dijkstra's algorithm. Edge weights must be non-negative.
SpannerAlgorithm.Spanner<E>, SpannerAlgorithm.SpannerImpl<E>| Constructor and Description |
|---|
GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph,
int k)
Constructs instance to compute a (2k-1)-spanner of an undirected graph.
|
| Modifier and Type | Method and Description |
|---|---|
SpannerAlgorithm.Spanner<E> |
getSpanner()
Computes a graph spanner.
|
public GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph, int k)
graph - an undirected graphk - positive integer.public SpannerAlgorithm.Spanner<E> getSpanner()
SpannerAlgorithmgetSpanner in interface SpannerAlgorithm<E>Copyright © 2017. All rights reserved.