Please use this identifier to cite or link to this item: doi:10.22028/D291-23754
Title: An efficient graph algorithm for dominance constraints
Author(s): Althaus, Ernst
Duchier, Denys
Koller, Alexander
Mehlhorn, Kurt
Niehren, Joachim
Thiel, Sven
Language: English
Year of Publication: 2003
OPUS Source: Journal of Algorithms, Volume 48, Issue 1, August 2003, Pages 194-219
SWD key words: Constraints
DDC notations: 004 Computer science, internet
Publikation type: Journal Article
Abstract: Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal dominance constraints and present an efficient graph algorithm for testing their satisfiablity in deterministic polynomial time. Previously, no polynomial time algorithm was known.
Link to this record: urn:nbn:de:bsz:291-scidok-2717
Date of registration: 24-Jun-2004
Faculty: SE - Sonstige Einrichtungen
Department: SE - Sonstige Einrichtungen
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
eff-dom.pdf257,68 kBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.