Importantly, a parser that employs our undirected inference algorithm can generate all possible trees, projective and non-projective.
the undirected MST problem ( § 2) has a randomized algorithm which is O(m) at expectation and with a very high probability ((Karger et al., 1995)), as well as an O(m • α(m, n)) worst-case deterministic algorithm (Pettie and Ramachandran, 2002), where α(m, n) is a certain natural inverse of Ackermann's function (Hazewinkel, 2001).