Package org.drip.graph.mst

Class SteeleCompleteUniformRandomEntry

java.lang.Object
org.drip.graph.mst.SteeleCompleteUniformRandomEntry
public class SteeleCompleteUniformRandomEntry
extends java.lang.Object
SteeleCompleteUniformRandomEntry holds a single Entry from the Expected MST Length Computation for Fully Connected Graphs with a small Number of Vertexes and Edge Weights that are i.i.d from U [0, 1]. 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
    SteeleCompleteUniformRandomEntry​(long mstLengthNumerator, long mstLengthDenominator)
    SteeleCompleteUniformRandomEntry Constructor

  • Method Summary

    Modifier and Type Method Description
    double approximateExpectedMSTLength()
    Retrieve the Approximate Expected MST Length
    long mstLengthDenominator()
    Retrieve the Denominator of the MST Length
    long mstLengthNumerator()
    Retrieve the Numerator of the MST Length

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • SteeleCompleteUniformRandomEntry

      public SteeleCompleteUniformRandomEntry​(long mstLengthNumerator, long mstLengthDenominator) throws java.lang.Exception
      SteeleCompleteUniformRandomEntry Constructor
      Parameters:
      mstLengthNumerator - Numerator of the MST Length
      mstLengthDenominator - Denominator of the MST Length
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • mstLengthNumerator

      public long mstLengthNumerator()
      Retrieve the Numerator of the MST Length
      Returns:
      Numerator of the MST Length

    • mstLengthDenominator

      public long mstLengthDenominator()
      Retrieve the Denominator of the MST Length
      Returns:
      Denominator of the MST Length

    • approximateExpectedMSTLength

      public double approximateExpectedMSTLength()
      Retrieve the Approximate Expected MST Length
      Returns:
      Approximate Expected MST Length