Tag: graphs
Fighting epidemics with the maximum spectral subgraph
Summary: Recent developments in mathematical epidemiology have identified a relationship between the time to extinction of an epidemic spreading over a network and the spectral radius of the underlying graph i.e. the largest eigenvalue of its adjacency matrix. At the same time, new generation networking technologies such as NFV ...
Reconfiguration Distribuée de Problèmes de Graphes
Summary: En théorie des graphes, un problème de configuration est le suivant : est-il possible d'aller d'une solution valide d'un problème à une autre, en passant par un chemin de solutions acceptables ? Quelle est la longueur minimale d'un chemin ? Quelle est la complexité ? Par exemple, un problème ...
Some recent results on the integer linear programming formulation for the Max-Cut problem
Summary: Given an undirected graph G=(V,E) where the edges are weighted by an arbitrary cost vector c, a cut S in G associated with a node subset S is the edge subset of E which contains all the edges having exactly one end-node in S. The Maximum Cut ...
Maximum Independent Set in H-free graphs
Summary: Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1 ...
Attribution Accessit du prix de thèse 2018 Graphes Charles DELORME
Nous avons le plaisir de vous annoncer que l'étudiant George Manoussakis encadré par Johanne Cohen et Antoine Deza a reçu l'accessit du prix de thèse 2018 Graphes Charles DELORME.
http://gtgraphes.labri.fr/pmwiki/pmwiki.php/PrixTheseDelorme/PrixTheseDelorme
Voici le résumé de sa thèse : Nous introduisons d'abord ...
Caractérisation de réseaux égocentrés par l'énumération de leurs sous-graphes induits
Résumé : La science des réseaux regroupe des méthodes issues de différentes disciplines qui ont néanmoins souvent du mal à percer au delà de celles-ci. Très utilisée en biologie moléculaire, notamment dans le cadre de l'étude des interactions entre protéines, l'énumération de l'ensemble des sous-graphes induits, jusqu'à ...
Mariage stable auto-stabilisant et distribué
Summary: Le problème du mariage stable (Stable Marriage problem, SMP) est un problème classique proposé pour la première fois par Gale et Shapley. Issu de l'économie, le SMP a aussi été étudié intensivement en maths et en informatique et a de multiples dérivés et applications (Cloud-computing, programme d'admission ...
Cycles dans les produits cartésiens de graphes
Résumé : Les cycles dans les graphes ont été largement étudiés : cycles hamiltoniens, cycles de toutes les longueurs, cycles contenant des sommets ou des arêtes donnés, .... Nous passons en revue quelques-uns des résultats essentiels du domaines avant de nous intéresser à l'existence de cycles dans les produits cartésiens de graphes ...
Le problème du voyageur canadien
Résumé : Le problème du voyageur canadien (PSPACE-complet), en anglais Canadian Traveller Problem (CTP), est un problème d'optimisation généralisant le problème du plus court chemin entre deux noeuds d'un graphe pondéré et non orienté. Un voyageur part d'un noeud s et son objectif est d'arriver à t ...
Victory du FHCP Challenge : Flinders Hamiltonian Cycle Project
Flinders Hamiltonian Cycle Project
The FHCP Challenge organised by the Flinders University (Adelaide, Australia) consisted in a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528 vertices, with an average size of just over 3000 vertices. This computational problem is one ...