Une contribution à la théorie des graphes (signés) borne d'homomorphisme et hamiltonicité
Cette soutenance aura lieu le mercredi 04 mai 2016 à 2:30pm en Salle 435 du LRI, Bâtiment 650 Ada Lovelace.
Le jury sera composé de:
Mme Liying KANG Professor Shanghai University (Examinateur)
M. Hao LI Directeur de Recherche CNRS Université Paris-Sud (Directeur de thèse)
M. Yannis MANOUSSAKIS Professor Université ...
VERTEX DISTINGUISHING COLORINGS OF GRAPHS
Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to ...
The coloring problem in clique-hypergraphs of graphs
ABSTRACT: A maximal clique of a graph is a clique not properly contained in any other clique. A \(k\)-clique coloring of a graph is an assignment of a \(k\) colors to the vertices of \(G\) such that no maximal clique with at least two vertices is monochromatic. The clique-chromatic ...
Prédiction de structure tridimensionnelle de molécules d’ARN par minimisation de regret
Cette soutenance aura lieu Vendredi 29 Avril 2016 à 14h00 Adresse de la soutenance : Université Paris Sud, Bât 650 Ada Lovelace, 91405 Orsay Cedex France - salle Salle 435
devant le jury composé de : Johanne COHEN Chargée de recherche Université Paris Sud 11 - Laboratoire LRI CoDirecteur de thèse
Alain DENISE Professeur ...
Minimizing the number of unhappy singles
Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties.
A matching M is said to be stable if there is ...
Euler Polytopes and Convex Matroid Optimization
We introduce a novel family of polytopes strengthening bounds relevant to combinatorial optimization and convex matroid optimization. Del Pia and Michini recently improved the upper bound of kd due to Kleinschmidt and Onn for the largest possible diameter of the convex hull of a set of points in dimension d ...
Starting of the OpenDreamKit Project
OpenDreamKit is a European project which was started in September 2015 and will run for four years. It includes 15 partner institutions in Europe and should provide substantial funding to the open source computational mathematics ecosystem, in particular the software Sage. It involves many members of GALaC. Indeed, it has ...
Prophet inequalities and secretary problem: a new approach.
In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...
Complexité de comptage des opérateurs d'intégration
L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...
Universal computation and asymptotic behaviour in symbolic dynamics.
Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...