[pt] O problema de particionamento de grafos em cliques ocorre freqüentemente em diversas áreas tais como Ciências sociais, Ciências Econômicas, Biologia, Análise de Agrupamentos e em todas as áreas onde é necessário a classificação de elementos. Estuda-se aqui os principais algoritmos exatos e as principais heurísticas que constam na literatura. É feita uma análise do desempenho das heurísticas no pior caso e apresenta-se uma classe especial de problemas para os quais o seu desempenho é arbitrariamente ruim. Apresentam-se quatro novas heurísticas para o problema, duas delas baseadas nos métodos conhecidos por simulated anneling e por tabu search. Elas são comparadas entre si através da análise dos resultados de suas aplicações a problemas-teste, a problemas que ocorre na realidade e a classe de problemas especiais mencionada acima. / [en] The clique partitioning problem arise very often in many fields as Social Science, Economics, Biology, Cluster analysis and in all other fields that need a classification of elements. The main exact algorithms and heuristics that appear in the literature are studied. A especial class of instances of the clique partitioning problem for which the most comonly used heuristics perform arbitrarily bad is exhibited. Four new heuristics are presented and two of them are based on the known simulated anneling and tabu search methods. They are analised by their application to test-problems, real-life-problems and to the special class of instances mentioned above

Les réseaux de neurones ont connu un vif regain d’intérêt avec le paradigme de l'apprentissageprofond ou deep learning. Alors que les réseaux dits optimisés, de par l'optimisation des paramètres nécessaires pour réaliser un apprentissage, nécessitent de fortes ressources de calcul, nous nous focalisons ici sur des réseaux de neurones dont l'architecture consiste en une mémoire au contenu adressable, appelées mémoires associatives neuronales. Le défi consiste à permettre la réalisation d'opérations traditionnellement obtenues par des calculs en s'appuyant exclusivement sur des mémoires, afin de limiter le besoin en ressources de calcul. Dans cette thèse, nous étudions une mémoire associative à base de clique, dont le codage neuronal parcimonieux optimise la diversité des données codées dans le réseau. Cette grande diversité permet au réseau à clique d'être plus performant que les autres mémoires associatives dans la récupération des messages stockés en mémoire. Les mémoires associatives sont connues pour leur incapacité à identifier sans ambiguïté les messages qu'elles ont préalablement appris. En effet, en fonction de l'information présente dans le réseau et de son codage, une mémoire peut échouer à retrouver le résultat recherché. Nous nous intéressons à cette problématique et proposons plusieurs contributions afin de réduire les ambiguïtés dans le réseau. Ces réseaux à clique sont en outre incapables de récupérer une information au sein de leurs mémoires si le message à retrouver est inconnu. Nous proposons une réponse à ce problème en introduisant une nouvelle mémoire associative à base de clique qui conserve la capacité correctrice du modèle initial tout en étant capable de hiérarchiser les informations. La hiérarchie s'appuie sur une transformation surjective bidirectionnelle permettant de généraliser une entrée inconnue à l'aide d'une approximation d'informations apprises. La validation expérimentale des mémoires associatives est le plus souvent réalisée sur des données artificielles de faibles dimensions. Dans le contexte de la vision par ordinateur, nous présentons ici les résultats obtenus avec des jeux de données plus réalistes etreprésentatifs de la littérature, tels que MNIST, Yale ou CIFAR. / The neural networks have gained a renewed interest through the deep learning paradigm. Whilethe so called optimised neural nets, by optimising the parameters necessary for learning, require massive computational resources, we focus here on neural nets designed as addressable content memories, or neural associative memories. The challenge consists in realising operations, traditionally obtained through computation, exclusively with neural memory in order to limit the need in computational resources. In this thesis, we study an associative memory based on cliques, whose sparse neural coding optimises the data diversity encoded in the network. This large diversity allows the clique based network to be more efficient in messages retrieval from its memory than other neural associative memories. The associative memories are known for their incapacity to identify without ambiguities the messages stored in a saturated memory. Indeed, depending of the information present in the network and its encoding, a memory can fail to retrieve a desired result. We are interested in tackle this issue and propose several contributions in order to reduce the ambiguities in the cliques based neural network. Besides, these cliques based nets are unable to retrieve an information within their memories if the message is unknown. We propose a solution to this problem through a new associative memory based on cliques which preserves the initial network's corrective ability while being able to hierarchise the information. The hierarchy relies on a surjective and bidirectional transition to generalise an unknown input with an approximation of learnt information. The associative memories' experimental validation is usually based on low dimension artificial dataset. In the computer vision context, we report here the results obtained with real datasets used in the state-of-the-art, such as MNIST, Yale or CIFAR.

From its introduction to its quindecennial, network coding have built a strong reputation in enhancing packet recovery process and achieving maximum information flow in both wires and wireless networks. Traditional studies focused on optimizing the throughput of the network by proposing complex schemes that achieve optimal delay. With the shift toward distributed computing at mobile devices, throughput and complexity become both critical factors that affect the efficiency of a coding scheme. Instantly decodable network coding imposed itself as a new paradigm in network coding that trades off this two aspects. This paper presents a survey of instantly decodable network coding schemes that are proposed in the literature. The various schemes are identified, categorized and evaluated. Two categories can be distinguished namely the conventional centralized schemes and the distributed or cooperative schemes. For each scheme, the comparison is carried out in terms of reliability, performance, complexity and packet selection methodology. Although the performance is generally inversely proportional to the computation complexity, numerous successful schemes from both the performance and complexity viewpoint are identified.

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

La détection de potentielles cibles secondaires ou off-targets d’un ligand donné requiert la détermination de son site d’interaction et la recherche de sites d’interaction similaires sur d’autres protéines. Dans le but de mener à bien cette étude, nous avons développé PatchSearch : cet outil compare un patch requête, correspondant à un site d’interaction, avec la surface d’une cible potentielle. L’algorithme employé s’appuie sur une méthode originale de recherche de quasi-cliques dans un graphe produit : cette approche identifie des groupes d’atomes du patch appariés avec ceux de la surface ciblée avec des propriétés physico-chimiques conservées et dans des configurations proches. Nous montrons que PatchSearch trouve des patches qui correspondent à ceux qui sont connus sur les surfaces ciblées. De plus, les résultats de l’application de PatchSearch sur des protéines flexibles indiquent que l’approche des quasi-cliques permet de retrouver à la fois les parties rigides et flexibles des patches,contrairement à la recherche classique de cliques. Enfin, les performances de Patch-Search sont équivalentes à celles des autres outils de comparaison de sites de liaison.Nous avons également appliqué PatchSearch sur des off-targets de médicaments impliqués dans le traitement de cancers. Nos expériences suggèrent l’utilisation de PatchSearch dans la recherche des éventuelles off-targets d’un médicament. / Detection of putative off-targets for a ligand requires to search for some similarbinding sites onto other proteins surface. In order to achieve this goal, we developeda tool named PatchSearch. This program compares a query patch, whichcontains the binding site, with the surface a potentially targeted protein. Patch-Search’s algorithm is based on an original method searching for some quasi-cliquesin a graph product, which identifies some atoms both in the patch and in the surfacewith conserved physicochemical properties and in similar configurations. Weshow that PatchSearch efficiently finds known patches on protein surfaces. Moreover,application of PatchSearch on flexible proteins shows that, unlike the classiccliques approach, quasi-cliques method allows to find both rigid and flexible partsof the patches. PatchSearch gets similar results compared to the other binding sitecomparison tools. We also applied PatchSearch to find patches binding polypharmacologicaldrugs involved in cancer treatment, in order to identify them on knownoff targets. Our experiments suggest to employ PatchSearch in off-targets detectionprocess.

The crossing number of a graph 𝐺 is the minimum number of crossings in any drawing of 𝐺 in the plane. The rectilinear crossing number of 𝐺 is the minimum number of crossings in any straight-line drawing of 𝐺. The Fáry-Wagner theorem states that planar graphs have rectilinear crossing number zero. By Wagner’s theorem, that is equivalent to stating that every graph that excludes 𝐾₅ and 𝐾₃,₃ as minors has rectilinear crossing number 0. We are interested in discovering other proper minor-closed families of graphs which admit strong upper bounds on their rectilinear crossing numbers. Unfortunately, it is known that the crossing number of 𝐾₃,ₙ with 𝑛 ≥ 1, which excludes 𝐾₅ as a minor, is quadratic in 𝑛, more specifically Ω(𝑛²). Since every 𝑛-vertex graph in a proper minor closed family has O(𝑛) edges, the rectilinear crossing number of all such graphs is trivially O(𝑛²). In fact, it is not hard to argue that O(𝑛) bound on the crossing number is the best one can hope for general enough proper minor-closed families of graphs and that to achieve O(𝑛) bounds, one has to both exclude a minor and bound the maximum degree of the graphs in the family. In this thesis, we do that for bounded degree graphs that exclude a single-crossing graph as a minor. A single-crossing graph is a graph whose crossing number is at most one. The main result of this thesis states that every graph 𝐺 that does not contain a single-crossing graph as a minor has a rectilinear crossing number O(∆𝑛), where 𝐺 has 𝑛 vertices and maximum degree ∆. This dependence on 𝑛 and ∆ is best possible. Note that each planar graph is a single-crossing graph, as is the complete graph 𝐾₅ and the complete bipartite graph 𝐾₃,₃. Thus, the result applies to 𝐾₅-minor-free graphs, 𝐾₃,₃-minor free graphs, as well as to bounded treewidth graphs. In the case of bounded treewidth graphs, the result improves on the previous best known bound of O(∆² · 𝑛) by Wood and Telle [New York Journal of Mathematics, 2007]. In the case of 𝐾₃,₃-minor free graphs, our result generalizes the result of Dujmovic, Kawarabayashi, Mohar and Wood [SCG 2008].

An E-graph is constructed by replacing each edge in a core graph G with a copy of a graph H. An important property of E-graphs is that their invariant values can be determined from parameters of the original graphs G and H. We determine chromatic number, clique number, vertex and edge cover numbers, vertex and edge independence numbers, circumference, and girth of E-graphs. A characterization of hamiltonian E-graphs is also given.

No description available.

No description available.

No description available.