For parsers that consider features of single links only, the Chu-Liu/Edmonds algorithm can be used instead.
this algorithm cannot be generalized to the second-order setting - McDonald and Pereira (2006) proved that this problem is NP-hard, and described an approximate greedy search algorithm.