Constraint models for graceful graphs |
| |
Authors: | Barbara M Smith Jean-François Puget |
| |
Affiliation: | 1.School of Computing,University of Leeds,Leeds,UK;2.ILOG, an IBM Company,Carry-le-Rouet,France |
| |
Abstract: | We present three constraint models of the problem of finding a graceful labelling of a graph, or proving that the graph is
not graceful. An experimental comparison of the models applied to different classes of graph is given. The first model seems
a natural way to represent the problem, but explores a much larger search tree than the other models. The second model does
much less search, by making the most constrained decisions first, but is slow because the constraints are time-consuming to
propagate. The third model combines the best features of the others, doing little more search than the second model while
being much the fastest of the three. The comparison of the three models provides a useful case-study of modelling problems
as constraint satisfaction problems. In addition, we show that constraint programming can be a useful tool for the study of
graceful graphs; the models presented here have contributed many new results. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|