Manuel Bodirsky

A New Algorithm for Normal Dominance Constraints

With Denys Duchier, Joachim Niehren and Sebastian Miele. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA04), pages 59-67, New Orleans.


We present an efficient algorithm that checks the consistency of partial descriptions of ordered trees. The constraint language of these descriptions was introduced by Cornell in computational linguistics; the constraints specify for pairs of nodes sets of admissible relative positions in an ordered tree. Cornell asked for an algorithm to find a tree structure satisfying these constraints. This computational problem generalizes the common-supertree problem that was studied in phylogenetic analysis, and also generalizes the network consistency problem of the so-called left-linear point algebra. We present the first polynomial time algorithm for Cornell's problem, which runs in time O(mn), where m is the number of constraints and n the number of variables in the input.


Download: a post-print is available in pdf.

Related papers

This paper deals with a problem that was introduced by Althaus, Duchier, Koller, Mehlhorn, Niehren and Thiel. It is strongly inspired by results and methods from the STACS 2002 paper titled "Pure Dominance Constraints" with Martin Kutz. The journal version of this important predecessor paper is also available here.

last modified 06/09 (Manuel Bodirsky)