Contraintes de Partitionnement par des Arbres

Résumé : Nous présentons deux contraintes qui partitionnent les sommets d'un graphe non-orienté G = (V, E), où |V| = n et |E| = m, en un ensemble d'arbres disjoints. La première contrainte, resource-forest, spécifie que chaque arbre dans la forêt doit contenir au moins un sommet ressource. L'ensemble des ressources est un sous-ensemble R ⊆ V. Cette contrainte est la contrepartie non-orienté de la contrainte d'arbre introduite dans [2], qui partitionne un graphe orienté en une forêt d'arbres orientés où seulement certains sommets peuvent être des racines. Nous décrivons un algorithme de consistance-hybride pour la contrainte resource-forest ayant une complexité de O(m + n). Ceci constitue donc une amélioration de la complexité en O(mn) connue pour le cas orienté. La seconde constrainte, proper-forest, est une variante de la première ne nécessitant pas que chaque arbre contienne une ressource. Cependant, tout arbre construit doit être un arbre propre, i.e., un arbre contenant au moins deux sommets. Nous avons développé un algorithme de consistance-hybride ayant une complexité en O(mn) au pire des cas, et en O(m√n) dans la plupart des autres cas.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085803
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 14:20:58
Dernière modification le : mardi 16 janvier 2018 - 14:38:49
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:09:37

Fichier

Identifiants

  • HAL Id : inria-00085803, version 1

Collections

Citation

Nicolas Beldiceanu, Xavier Lorca, Irit Katriel. Contraintes de Partitionnement par des Arbres. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085803〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

55