Eingang zum Volltext in SciDok
Hinweis zum Urheberrecht
InProceedings (Aufsatz / Paper einer Konferenz etc.) zugänglich unter
A new algorithm for normal dominance constraints
URN: urn:nbn:de:bsz:291-scidok-2578
URL: http://scidok.sulb.uni-saarland.de/volltexte/2004/257/
Quelle:
(2004) ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, January 11-13, 2004.
pdf-Format:
Dokument 1.pdf (161 KB)
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.