Tag: Team seminar
graph algorithms to help molecular construction
Summary: In organic chemistry, when a new molecule is designed, it is necessary to determine chemical reactions that can be used to synthesize this target molecule from available compounds. Finding such chemical reactions consists usually in searching in a reaction database (such as REAXYS or ChEBI) for a molecule that ...
Sur le nombre des (d,k)-polytopes
Résumé :
Un polytope est l'enveloppe convexe d'un ensemble fini de points dans un espace euclidien. On dénotera par (d,k)-polytope un polytope entier de dimension d de R^d et contenu dans l'hypercube [0,k]^d. Ce sont des objets faciles à décrire mais dont la ...
Economics of Age of Information (AoI) Management: Pricing and Competition
Summary: Fueled by the rapid development of communication networks and sensors in portable devices, today many mobile users are invited by content providers to sense and send back real-time useful information (e.g., traffic observations and sensor data) to keep the freshness of the online platforms’ content updates. However, due ...
Expérimentations sur le calcul hautes performances en combinatoire énumérative et algébrique.
Summary :
In this talk, I will report on several experiments around large scale enumerations in enumerative and algebraic combinatorics.
I'll describe a methodology used to achieve large speedups in several enumeration problems. Indeed, in many combinatorial structures (permutations, partitions, monomials, young tableaux), the data can be encoded as a ...
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 ...
Self-Stabilization and Byzantine Tolerance for Maximal Matching
Summary: We analyse the impact of transient and Byzantine faults on the construction of a maximal matching in a general network. In particular, we consider the self-stabilizing algorithm called AnonyMatch presented by Cohen et al. in PPL'2016 for computing such a matching. Since self-stabilization is transient fault tolerant, we ...
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 ...
De la sociologie avec des algorithmes à la sociologie des algorithmes
Summary:
La décennie 2000 a vu l’émergence d’une sociologie parfois dite computationnelle, sociologie qui s’appuie sur des traces collectées numériquement en très grandes quantités, nécessitant des algorithmes spécifiques. En passant en revue quelques exemples de cette sociologie avec des algorithmes, je montrerai comment cet aperçu laisse voir ...
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 ...