Please use this identifier to cite or link to this item: doi:10.22028/D291-25764
Title: A new algorithm for normal dominance constraints
Author(s): Bodirsky, Manuel
Duchier, Denys
Miele, Sebastian
Niehren, Joachim
Language: English
Year of Publication: 2004
OPUS Source: ACM-SIAM Symposium on Discrete Algorithms (SODA04), New Orleans, January 11-13, 2004.
SWD key words: ASL <Programmiersprache>
DDC notations: 004 Computer science, internet
Publikation type: Conference Paper
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 to this record: urn:nbn:de:bsz:291-scidok-2578
Date of registration: 18-Jun-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
wndc.pdf160,69 kBAdobe PDFView/Open

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