Package org.drip.graph.decisiontree

Class ValidationComplexity

java.lang.Object
org.drip.graph.decisiontree.ValidationComplexity
public class ValidationComplexity
extends java.lang.Object
ValidationComplexity implements the Asymptotic Size Complexity O (n) for Decision Tree Validation. The References are:

  • Bader, D. A., and G. Cong (2006): Fast Shared Memory Algorithms for computing the Minimum Spanning Forests of Sparse Graphs Journal of Parallel and Distributed Computing 66 (11) 1366-1378
  • Chazelle, B. (2000): A Minimum Spanning Tree ALgorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
  • Karger, D. R., P. N. Klein, and R. E. Tarjan (1995): A Randomized Linear-Time Algorithm to find Minimum Spanning Trees Journal of the Association for Computing Machinery 42 (2) 321-328
  • Pettie, S., and V. Ramachandran (2002): An Optimal Minimum Spanning Tree Algorithm Journal of the ACM 49 (1) 16-34
  • Wikipedia (2020): Minimum Spanning Tree https://en.wikipedia.org/wiki/Minimum_spanning_tree




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    ValidationComplexity​(double edgeWeightPermutationsUpperBound, double mstRuntimeUpperBound, double permutationsCheckUpperBound)
    ValidationComplexity Constructor

  • Method Summary

    Modifier and Type Method Description
    double edgeWeightPermutationsUpperBound()
    Retrieve the Upper Bound on the Number of Edge Weight Permutations
    double mstRuntimeUpperBound()
    Retrieve the Upper Bound on the MST Algorithm Runtime
    double permutationsCheckUpperBound()
    Retrieve the Upper Bound on the Time required to check all Permutations

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • ValidationComplexity

      public ValidationComplexity​(double edgeWeightPermutationsUpperBound, double mstRuntimeUpperBound, double permutationsCheckUpperBound) throws java.lang.Exception
      ValidationComplexity Constructor
      Parameters:
      edgeWeightPermutationsUpperBound - Upper Bound on the Number of Edge Weight Permutations
      mstRuntimeUpperBound - Upper Bound on the MST Algorithm Runtime
      permutationsCheckUpperBound - Upper Bound on the Time required to check all Permutations
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • edgeWeightPermutationsUpperBound

      public double edgeWeightPermutationsUpperBound()
      Retrieve the Upper Bound on the Number of Edge Weight Permutations
      Returns:
      Upper Bound on the Number of Edge Weight Permutations

    • mstRuntimeUpperBound

      public double mstRuntimeUpperBound()
      Retrieve the Upper Bound on the MST Algorithm Runtime
      Returns:
      Upper Bound on the MST Algorithm Runtime

    • permutationsCheckUpperBound

      public double permutationsCheckUpperBound()
      Retrieve the Upper Bound on the Time required to check all Permutations
      Returns:
      Upper Bound on the Time required to check all Permutations