On the Relevance of Optimal Tree Decompositions for Constraint Networks - Archive ouverte HAL Access content directly
Conference Papers Year :

On the Relevance of Optimal Tree Decompositions for Constraint Networks

(1) , (2) , (1)
1
2

Abstract

For the study and the solving of NP-hard problems, the concept of tree decomposition is nowadays a major topic in Computer Science, in Artificial Intelligence and particularly in Constraint Programming. It appears as a promising field for the theoretical study of numerous graphical models like Bayesian Networks or (Weighted) Constraint Networks, since it can ensure, under some hypothesis, the existence of polynomial time algorithms. This concept is also used in a wide range of applications. Recently, a real improvement in the practical computation of optimal tree decompositions has been observed, allowing new promising applications of this concept in real applications. In this paper, we first aim to analyze the real relevance of such optimal decompositions. We first set that a larger set of instances are now optimally decomposable in practice but using these algorithms on a practical level still constitutes a real difficulty. In a second time, we assess the impact of such optimal decompositions for solving these instances and note a discrepancy between the empirical results and what is expected from the complexity analysis. Finally, we discuss of the next investigations which are needed on this topic.
Fichier principal
Vignette du fichier
ictai2018_final_V2.pdf (609.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01933665 , version 1 (23-11-2018)

Identifiers

  • HAL Id : hal-01933665 , version 1

Cite

Philippe Jégou, Hélène Kanso, Cyril Terrioux. On the Relevance of Optimal Tree Decompositions for Constraint Networks. Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2018, Volos, Greece. ⟨hal-01933665⟩
107 View
222 Download

Share

Gmail Facebook Twitter LinkedIn More