Class GreedyMultiplicativeSpanner<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    @Deprecated
    public class GreedyMultiplicativeSpanner<V,​E>
    extends java.lang.Object
    Deprecated.
    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
    • Field Detail

      • edgeList

        private final java.util.Set<E> edgeList
        Deprecated.
      • k

        private final int k
        Deprecated.
    • Constructor Detail

      • GreedyMultiplicativeSpanner

        public GreedyMultiplicativeSpanner​(UndirectedGraph<V,​E> graph,
                                           int k)
        Deprecated.
        Constructs instance to compute a (2k-1)-spanner of a graph.
        Parameters:
        graph - the input graph
        k - positive integer.
    • Method Detail

      • getSpannerEdgeSet

        public java.util.Set<E> getSpannerEdgeSet()
        Deprecated.
        Get the edge set of the spanner.
        Returns:
        the set of edges of the spanner