CS @ CU CS @ CU

An Efficient Graph Algorithm for Dominance Constraints

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

Journal 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