Module org.jgrapht.core
Package org.jgrapht.alg.spanning

Class GreedyMultiplicativeSpanner<V,​E>

java.lang.Object
org.jgrapht.alg.spanning.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 java.lang.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} + n \log n))$ time by using Dijkstra's algorithm. Edge weights must be non-negative.

Author:
Dimitrios Michail

  • Constructor Details

    • GreedyMultiplicativeSpanner

      public GreedyMultiplicativeSpanner​(Graph<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.
      Throws:
      java.lang.IllegalArgumentException - if the graph is not undirected
      java.lang.IllegalArgumentException - if k is not positive

  • Method Details