Publication details

Programming Systems

Gert Smolka

Publications

Teaching

Software

Formalizations

A New Algorithm for Normal Dominance Constraints

Manuel Bodirsky, Denys Duchier, Sebastian Miele, Joachim Niehren

ACM-SIAM Symposium on Discrete Algorithms, pp. 54-78, The ACM Press, January 2004

Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.

Download PDF        Show BibTeX               

@INPROCEEDINGS{superdom,
  title = {A New Algorithm for Normal Dominance Constraints},
  author = {Manuel Bodirsky and Denys Duchier and Sebastian Miele and Joachim Niehren},
  year = {2004},
  month = {jan},
  publisher = {{The {ACM} Press}},
  booktitle = {ACM-SIAM Symposium on Discrete Algorithms},
  pages = {{54-78}},
  note = {{accepted version of feb 2003.}},
}

Login to edit