An Ecien t Graph Algorithm for Dominance Constraints 1
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel · 2003
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisabilit y problem is known to be NPcomplete. Here we identify normal dominance constraints and present an ecien t graph algorithm for testing their satisabilit y in deterministic polynomial time. Previously, no polynomial time algorithm was known.