SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

InProceedings (Aufsatz / Paper einer Konferenz etc.) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-2578
URL: http://scidok.sulb.uni-saarland.de/volltexte/2004/257/


A new algorithm for normal dominance constraints

Bodirsky, Manuel ; Duchier, Denys ; Miele, Sebastian ; Niehren, Joachim

Quelle: (2004) ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, January 11-13, 2004.
pdf-Format:
Dokument 1.pdf (161 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: ASL <Programmiersprache>
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Sprache: Englisch
Erstellungsjahr: 2004
Publikationsdatum: 18.06.2004
Kurzfassung auf Englisch: 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.

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English