Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

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               

@ARTICLE{eff-dom,
  title = {An Efficient Graph Algorithm for Dominance Constraints},
  author = {Ernst Althaus and Denys Duchier and Alexander Koller and Kurt Mehlhorn and Joachim Niehren and Sven Thiel},
  year = {2003},
  month = {may},
  journal = {{Journal of Algorithms}},
  booktitle = {Journal of Algorithms},
  volume = {{48}},
  pages = {{194--219}},
  number = {{1}},
  note = {{Special Issue of SODA 2001.}},
}

Login to edit