Transformations de graphes et nombre de stabilite (French text).

摘要

The maximum stable set problem consist of finding a subset of pairwise nonadjacent vertices. The maximum cardinality of such a set in a graph is called the stability number of the graph. This masters thesis is about solving this NP-hard problem using graph transformations. With this approach, we seek to reduce the computation cost of the problem in some graphs.; We define graph transformations and present some examples. We also define two types of graph transformations: exact and inexact. A graph transformation is exact if its incidence on the stability number is constant independently of the graph on which it is applied. Otherwise, the graph transformation is inexact. We propose two strategies for solving the maximum stable set problem. One uses exact graph transformations and the other uses inexact graph transformations.; We report and discuss the experimental results of the use of three exact graph transformations before solving the maximum stable set problem. We present the method developed to evaluate the incidence of graph transformations on the computational cost of the problem. (Abstract shortened by UMI.)