November 27 2014
Partial order may be represented as a directed graph. (no cycles)
Given any directed acyclic graph G,
G: u -> v -> w -> x
Now, u -> w, u -> x, v -> x
Also, u -> u, v -> v, w -> w, and x -> x
Computed via 'matrix multiplication'
[ u v w x ] * [ u ]
[ v ]
[ w ]
[ x ]
Time proportional to n^3,
( Strassen '69 managed O(n^2.81) )
( '90 managed O(n^2.375) )
( Williams '13 managed O(n^2.3727) )
Only: u -> v -> w -> x
Corrosponds to the 'covering relation' which is the haas
which, is unique.
Closure and reduction, represesents 'reachability'