Tag: Team seminar
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 ...
Binary pattern of length greater than 14 are abelian-2-avoidable
Summary: Two words u and v are abelian equivalent if they are permutation of each other ("aabc" and "baca" are abelian equivalent). Let w be a word and P= P1...Pn (where the Pi are the letters of P) a pattern (a word over another alphabet), we say that w ...
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 ...
A Two-level Auction for Resource Allocation in Multi-tenant C-RAN
Summary: Next generation (5G) mobile networks are targeting twenty five-fold data rates provided by the current generation of mobile networks, with higher efficiency, enhanced mobility support and seamless management of connected devices. In order to provide such features, at reduced Capital Expenditure (CAPEX) and Operational Expenditure (OPEX), the Cloud- RAN ...
Binary pattern of length greater than 14 are abelian-2-avoidable
Summary: Two words u and v are abelian equivalent if they are permutation of each other ("aabc" and "baca" are abelian equivalent). Let w be a word and P= P1...Pn (where the Pi are the letters of P) a pattern (a word over another alphabet), we say that w ...
A concurrent lock-free algorithm for computing a finite semigroup
Summary: In this talk I will present a concurrent lock-free version of the Froidure-Pin Algorithm for computing a finite semigroup. This algorithm computes a subsemigroup S generated by some given elements of a finite semigroup of a certain type, such as transformations, partial permutations, square matrices over a semiring, bipartitions ...
Calculer le taux de croissance du nombre de motifs d'un pavage
Résumé :
Les pavages correspondent à des coloriages d'une grille (Z ou Z^d) qui obéissent à des contraintes locales. Compter ou énumérer les coloriages admissibles de sous-ensembles finis est une question combinatoire naturelle, et le taux de croissance de ce nombre correspond à une notion d'entropie qui apparait ...
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 ...