• search hit 14 of 28
Back to Result List

A New Algorithm for Normal Dominance Constraints

Please always quote using this URN:urn:nbn:de:0296-matheon-2769
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Manuel Bodirsky, Denys Duchier, Sebastian Miehle, Joachim Niehren
URN:urn:nbn:de:0296-matheon-2769
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:280
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.