An Efficient Graph Algorithm for Dominance Constraints

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

Journal of Algorithms, 48(1):194-219, 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

BibTeX Entry
@article{eff-dom,
	Author = {Ernst Althaus and Denys Duchier and Alexander Koller and Kurt Mehlhorn and Joachim Niehren and Sven Thiel},
	Journal = {Journal of Algorithms},
	Number = 1,
	Pages = {194--219},
	Title = {An Efficient Graph Algorithm for Dominance Constraints},
	Volume = 48,
	Year = 2003
}

Back: Publications