Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25764
Titel: A new algorithm for normal dominance constraints
Verfasser: 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.
SWD-Schlagwörter: ASL <Programmiersprache>
DDC-Sachgruppe: 004 Informatik
Dokumentart : InProceedings (Aufsatz / Paper einer Konferenz etc.)
Kurzfassung: 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
SciDok-Publikation: 18-Jun-2004
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
wndc.pdf160,69 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.