- -- size (Tk) = max (for w in W) (length (w)) but the table
- -- lookups are replaced by multiplications.
-
- -- where Tk values are randomly generated. n is defined later on
- -- but the algorithm recommends to use a value a little bit
- -- greater than 2m. Note that for large values of m, the main
- -- memory space requirements comes from the memory space for
- -- storing function g (>= 2m entries).
-
- -- Random graphs are frequently used to solve difficult problems
- -- that do not have polynomial solutions. This algorithm is based
- -- on a weighted undirected graph. It comprises two steps: mapping
- -- and assigment.
-
- -- In the mapping step, a graph G = (V, E) is constructed, where V
- -- = {0, 1, ..., n-1} and E = {(for w in W) (f1 (w), f2 (w))}. In
- -- order for the assignment step to be successful, G has to be
- -- acyclic. To have a high probability of generating an acyclic
- -- graph, n >= 2m. If it is not acyclic, Tk have to be regenerated.
-
- -- In the assignment step, the algorithm builds function g. As G
- -- is acyclic, there is a vertex v1 with only one neighbor v2. Let
- -- w_i be the word such that v1 = f1 (w_i) and v2 = f2 (w_i). Let
- -- g (v1) = 0 by construction and g (v2) = (i - g (v1)) mod n (or
- -- to be general, (h (i) - g (v1) mod n). If word w_j is such that
- -- v2 = f1 (w_j) and v3 = f2 (w_j), g (v3) = (j - g (v2)) mod n
- -- (or to be general, (h (j) - g (v2)) mod n). If w_i has no
- -- neighbor, then another vertex is selected. The algorithm
- -- traverses G to assign values to all the vertices. It cannot
- -- assign a value to an already assigned vertex as G is acyclic.
+ -- size (Tk) = max (for w in W) (length (w)) but the table lookups are
+ -- replaced by multiplications.
+
+ -- where Tk values are randomly generated. n is defined later on but the
+ -- algorithm recommends to use a value a little bit greater than 2m. Note
+ -- that for large values of m, the main memory space requirements comes
+ -- from the memory space for storing function g (>= 2m entries).
+
+ -- Random graphs are frequently used to solve difficult problems that do
+ -- not have polynomial solutions. This algorithm is based on a weighted
+ -- undirected graph. It comprises two steps: mapping and assignment.
+
+ -- In the mapping step, a graph G = (V, E) is constructed, where = {0, 1,
+ -- ..., n-1} and E = {(for w in W) (f1 (w), f2 (w))}. In order for the
+ -- assignment step to be successful, G has to be acyclic. To have a high
+ -- probability of generating an acyclic graph, n >= 2m. If it is not
+ -- acyclic, Tk have to be regenerated.
+
+ -- In the assignment step, the algorithm builds function g. As G is
+ -- acyclic, there is a vertex v1 with only one neighbor v2. Let w_i be
+ -- the word such that v1 = f1 (w_i) and v2 = f2 (w_i). Let g (v1) = 0 by
+ -- construction and g (v2) = (i - g (v1)) mod n (or h (i) - g (v1) mod n).
+ -- If word w_j is such that v2 = f1 (w_j) and v3 = f2 (w_j), g (v3) = (j -
+ -- g (v2)) mod (or to be general, (h (j) - g (v2)) mod n). If w_i has no
+ -- neighbor, then another vertex is selected. The algorithm traverses G to
+ -- assign values to all the vertices. It cannot assign a value to an
+ -- already assigned vertex as G is acyclic.