A New Algorithm for Normal Dominance Constraints

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.
Type de document :
Communication dans un congrès
J. Ian Munro. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. ACM Press, pp.59-67, 2004, SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 〈http://portal.acm.org/citation.cfm?id=982801〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536536
Contributeur : Joachim Niehren <>
Soumis le : jeudi 18 novembre 2010 - 16:36:01
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : samedi 19 février 2011 - 02:45:17

Fichier

wndc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536536, version 1

Citation

Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele. A New Algorithm for Normal Dominance Constraints. J. Ian Munro. ACM-SIAM Symposium on Discrete Algorithms - SODA'2003, Jan 2004, New Orleans, Louisiana, United States. ACM Press, pp.59-67, 2004, SODA '04 Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 〈http://portal.acm.org/citation.cfm?id=982801〉. 〈inria-00536536〉

Partager

Métriques

Consultations de la notice

385

Téléchargements de fichiers

178