An Efficient Graph Algorithm for Dominance Constraints
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, and Sven ThielJournal of Algorithms. To appear, 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:
Download (140 K)
BibTex Entry
@Misc{AltDucKolMehNieThi03, author = {Ernst Althaus and Denys Duchier and Alexander Koller and Kurt Mehlhorn and Joachim Niehren and Sven Thiel}, title = {An Efficient Graph Algorithm for Dominance Constraints}, year = 2003, howpublished = {Journal of Algorithms. To appear} }
Back: Publications