Package org.drip.graph.mstgreedy

Class ReverseDeleteGenerator<V>

java.lang.Object
org.drip.graph.treebuilder.OptimalSpanningForestGenerator
org.drip.graph.mstgreedy.ReverseDeleteGenerator<V>
public class ReverseDeleteGenerator<V>
extends OptimalSpanningForestGenerator
ReverseDeleteGenerator implements the Reverse-Delete Algorithm for generating a Minimum Spanning Tree. The References are:

  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Kleinberg, J., and E. Tardos (2006): Algorithm Design Addison Wesley
  • Kruskal, J. B. (1956): On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem Proceedings of the American Mathematical Society 7 (1) 48-50
  • Thorup, M. (2000): Near-optimal Fully-dynamic Graph Connectivity Proceedings on the 32nd ACM Symposium on the Theory of Computing 343-350
  • Wikipedia (2019): Reverse-delete Algorithm https://en.wikipedia.org/wiki/Reverse-delete_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    ReverseDeleteGenerator​(Directed<?> graph, boolean maximum)
    ReverseDeleteGenerator Constructor

  • Method Summary

    Modifier and Type Method Description
    Forest<?> optimalSpanningForest()
    Generate the Optimal Spanning Forest

    Methods inherited from class org.drip.graph.treebuilder.OptimalSpanningForestGenerator

    graph, maximum

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ReverseDeleteGenerator

      public ReverseDeleteGenerator​(Directed<?> graph, boolean maximum) throws java.lang.Exception
      ReverseDeleteGenerator Constructor
      Parameters:
      graph - The Graph
      maximum - TRUE - The Maximum Spanning Forest is to be generated
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details