org.jgrapht.alg.spanning

## Class GreedyMultiplicativeSpanner<V,E>

• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Implemented Interfaces:
SpannerAlgorithm<E>

```public class GreedyMultiplicativeSpanner<V,E>
extends Object
implements SpannerAlgorithm<E>```
Greedy algorithm for (2k-1)-multiplicative spanner construction (for any integer k >= 1).

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.

Since:
July 15, 2016
Author:
Dimitrios Michail

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.SpannerAlgorithm

`SpannerAlgorithm.Spanner<E>, SpannerAlgorithm.SpannerImpl<E>`
• ### Constructor Summary

Constructors
Constructor and Description
```GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph, int k)```
Constructs instance to compute a (2k-1)-spanner of an undirected graph.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`SpannerAlgorithm.Spanner<E>` `getSpanner()`
Computes a graph spanner.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### GreedyMultiplicativeSpanner

```public GreedyMultiplicativeSpanner(UndirectedGraph<V,E> graph,
int k)```
Constructs instance to compute a (2k-1)-spanner of an undirected graph.
Parameters:
`graph` - an undirected graph
`k` - positive integer.
• ### Method Detail

• #### getSpanner

`public SpannerAlgorithm.Spanner<E> getSpanner()`
Description copied from interface: `SpannerAlgorithm`
Computes a graph spanner.
Specified by:
`getSpanner` in interface `SpannerAlgorithm<E>`
Returns:
a graph spanner