%
% GENERATED FROM https://www.coli.uni-saarland.de
%    by   : anonymous
%    IP   : coli2006.lst.uni-saarland.de
%    at   : Mon, 05 Feb 2024 15:42:54 +0100 GMT
%    
% Selection : Reference #16
%




@Article{Althaus_et_al:2003,
      AUTHOR = {Althaus, Ernst and Duchier, Denys and Koller, Alexander and Mehlhorn, Kurt and Niehren, Joachim and Thiel, Sven},
      TITLE = {An Efficient Graph Algorithm for Dominance Constraints},
      YEAR = {2003},
      JOURNAL = {Journal of Algorithms},
      VOLUME = {48},
      PAGES = {194--219},
      URL = {https://www.coli.uni-saarland.de/~koller/papers/eff-dom.ps.gz},
      ABSTRACT = {Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.},
      ANNOTE = {COLIURL : Althaus:19xx:EGA.pdf Althaus:19xx:EGA.ps}
}