Paper: Graph Branch Algorithm: An Optimum Tree Search Method For Scored Dependency Graph With Arc Co-Occurrence Constraints

ACL ID P06-2047
Title Graph Branch Algorithm: An Optimum Tree Search Method For Scored Dependency Graph With Arc Co-Occurrence Constraints
Venue Annual Meeting of the Association of Computational Linguistics
Session Poster Session
Year 2006
Authors

Various kinds of scored dependency graphs are proposed as packed shared data structures in combination with optimum dependency tree search algorithms. This paper classifies the scored dependency graphs and discusses the specific features of the “Dependency Forest” (DF) which is the packed shared data structure adopted in the “Preference Dependency Grammar” (PDG), and proposes the “Graph Branch Algorithm” for computing the optimum dependency tree from a DF. This paper also reports the experiment showing the computational amount and behavior of the graph branch algorithm.