Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25764
Titel: | A new algorithm for normal dominance constraints |
VerfasserIn: | Bodirsky, Manuel Duchier, Denys Miele, Sebastian Niehren, Joachim |
Sprache: | Englisch |
Erscheinungsjahr: | 2004 |
Quelle: | ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, January 11-13, 2004. |
Kontrollierte Schlagwörter: | ASL <Programmiersprache> |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Konferenzbeitrag (in einem Konferenzband / InProceedings erschienener Beitrag) |
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 zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-2578 hdl:20.500.11880/25820 http://dx.doi.org/10.22028/D291-25764 |
Datum des Eintrags: | 18-Jun-2004 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
wndc.pdf | 160,69 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.