@inproceedings{cao-etal-2017-parsing,
    title = "Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs",
    author = "Cao, Junjie  and
      Huang, Sheng  and
      Sun, Weiwei  and
      Wan, Xiaojun",
    editor = "Barzilay, Regina  and
      Kan, Min-Yen",
    booktitle = "Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
    month = jul,
    year = "2017",
    address = "Vancouver, Canada",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/fix-sig-urls/P17-1193/",
    doi = "10.18653/v1/P17-1193",
    pages = "2110--2120",
    abstract = "We study the Maximum Subgraph problem in deep dependency parsing. We consider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2. Our main contribution is an exact algorithm that obtains maximum subgraphs satisfying both restrictions simultaneously in time O(n5). Moreover, ignoring one linguistically-rare structure descreases the complexity to O(n4). We also extend our quartic-time algorithm into a practical parser with a discriminative disambiguation model and evaluate its performance on four linguistic data sets used in semantic dependency parsing."
}