A New Algorithm for Normal Dominance Constraints
Please always quote using this URN:urn:nbn:de:0296-matheon-2769
- 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.
Author: | Manuel Bodirsky, Denys Duchier, Sebastian Miehle, Joachim Niehren |
---|---|
URN: | urn:nbn:de:0296-matheon-2769 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 280 |