Please use this identifier to cite or link to this item:
doi:10.22028/D291-25764
Title: | A new algorithm for normal dominance constraints |
Author(s): | Bodirsky, Manuel Duchier, Denys Miele, Sebastian Niehren, Joachim |
Language: | English |
Year of Publication: | 2004 |
OPUS Source: | ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, January 11-13, 2004. |
SWD key words: | ASL <Programmiersprache> |
DDC notations: | 004 Computer science, internet |
Publikation type: | Conference Paper |
Abstract: | 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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-2578 hdl:20.500.11880/25820 http://dx.doi.org/10.22028/D291-25764 |
Date of registration: | 18-Jun-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.