HDR de Hamida Seba

Sujet :
Graph-based Representations in Matchmaking and Networking

Résumé :

Graphs are universal modeling tools. They are used both to represent objects and to formalize problems in several domains such as pattern recognition, scheduling, etc. One of the strengths of this modeling tool is its graphic and visual representation that can greatly help to see the intricacies and peculiarities of represented objects or the special cases of the modeled problem. This work is a collection of contributions based on graph representations in two domains: 1. Comparison of complex objects that becomes, in this context, a problem of graph comparison or graph matching. Graph matching has been the subject of several investigations, especially in pattern recognition and in applications where the notion of graph is used as an abstract representation of a data model: database schema, semantic web, service-oriented architectures (ontologies and process models), etc. We first studied the classes of graphs manipulated by these data models to find the most efficient matching algorithms. We worked on approaches based on graph partitioning to define similarity measures suitable for this type of graphs. We also searched specific structures in these graphs that may increase the accuracy of the matching. We used the concept of functional module as a matching unit. We also focused on the scalability problem of graph comparison within two directions: (1) the size of graphs by considering the problems related to large graph comparison for which almost all matching methods are powerless in terms of scalability. We have shown that with modular decomposition, we can obtain a compact encoding of graphs called prime graphs. Simple and small, these graphs are a very good representation of large graphs inmatching. Thus one can apply directly comparison algorithms on the prime graphs, without decompressing them, to obtain an approximation of the distance between the original graphs. (2) the number of graphs mainly within the project IMU-kite whose core interest is the processing of a large number of graphs representing images. For this, we have developedmulti-level approaches with the aimof reducing the number of candidates at each level using criteria that consume less computing time and memory space in the first levels of the approach. 2. The logical organization of wireless communication networks especially mobile ad hoc networks and wireless sensor networks. These organizations such as logical topologies have multiple applications. They help the design of communication protocols without worrying about the constraints related to the real physical network topology. They are also used in scheduling and resource assignment problems such as the assignment of communication channels (frequencies or timeslots), etc. We studied several clustering criteria such as trust relationships between nodes, graph alliances, etc., with applications in group communication and packet aggregation in sensor networks. We also looked at graph coloring as a main graph clustering method. We studied several types of coloring and proposed solutions, both on the number of colors, coloring algorithms and graph classes. We have therefore provided solutions for the problem of distance edge coloring, set coloring and edge coloring by total labeling with applications in timeslot assignement.

Date de soutenance : vendredi, 10 octobre, 2014