Context:
Although the problem of graph editing (CE) has been defined since 1964, it is still very much studied. One of the reasons is that the graph editing problem occurs in many applications such as, for example, species analysis, a problem in the field of genetics. The difficulty is to choose a representation that guarantees an effective treatment of this problem. Several representations have emerged, such as the one that uses: the logic of the propositions (SAT) and its extensions (2-SAT, 3-SAT, MAX-SAT, ...), the formalism of the problem of satisfaction of the CSP constraints.
Contribution:
Our contribution in the field of the classification under constraints is varied according to two main axes:
Results:
the goal is to propose a new approach to deal with graph editing. This approach is based on the formalism of the problems of satisfaction of valued constraints.
This formalism provides a rigorous framework, more general than that of the CSP and especially powerful algorithms to efficiently solve combinatorial problems.
Publications:
Technical environment:
ToolBar2, C ++, Python