Publication details

Saarland University Computer Science

An Efficient Graph Algorithm for Dominance Constraints

Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel

Journal of Algorithms, pp. 194--219, May 2003

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.

Download PDF        Show BibTeX               

Login to edit

Legal notice, Privacy policy