F Nous contacter

0

Documents  Gittenberger, Bernhard | enregistrements trouvés : 6

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

2 y

Research School

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

V

- xv; 554 p.
ISBN 978-3-7643-7128-9

Trends in mathematics

Localisation : Colloque 1er étage (Vien/2004)

informatique # arbre # algorithme # combinatoire # générateur de nombres aléatoires # optimisation # évaluation de la performance

05-XX ; 60C05 ; 60Gxx ; 68P30 ; 68Q25 ; 68Rxx ; 68W20 ; 68W40 ; 90B15 ; 68-06 ; 68R10 ; 68R05 ; 00B25

... Lire [+]

y

Research School

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

y

Research School

Une urne de Pólya est un processus stochastique décrivant la composition d'une urne contenant des boules de différentes couleurs. L'ensemble des couleurs est usuellement un ensemble fini {1, ..., d}. A chaque instant n, une boule est tirée uniformément au hasard dans l'urne (notons c sa couleur), remise dans l'urne accompagnée de R(c,i) boules de couleur i pour toute couleur i.
Je présente dans cet exposé une généralisation de ce modèle à un ensemble infini, et même potentiellement indénombrable de couleurs. Dans ce nouveau modèle, la composition de l'urne est une mesure (potentiellement non-atomique) sur un espace Polonais.
Ceci est un travail en collaboration avec Jean-François Marckert.
Une urne de Pólya est un processus stochastique décrivant la composition d'une urne contenant des boules de différentes couleurs. L'ensemble des couleurs est usuellement un ensemble fini {1, ..., d}. A chaque instant n, une boule est tirée uniformément au hasard dans l'urne (notons c sa couleur), remise dans l'urne accompagnée de R(c,i) boules de couleur i pour toute couleur i.
Je présente dans cet exposé une généralisation de ce modèle à un ...

60J80

... Lire [+]

y

Research School

We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show that the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance, while formerly it was only known that it is linear with high probability.
This is based on a joint work with Marc Noy (UPC) and Clément Requilé (FU Berlin - BMS).
We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show ...

05C80 ; 05C10 ; 05A16

... Lire [+]

y

Research School

Dans une première partie, je présenterai différentes problématiques liées à des statistiques d'occurrences de mots dans des génomes et décortiquerai plus en détail la question de savoir comment détecter si un mot a une fréquence d'apparition significativement anormale dans une séquence. Dans une deuxième partie, je présenterai différentes extensions pour tenir compte du fait qu'un motif d'ADN fonctionnel n'est pas toujours un « mot », mais qu'il peut avoir une structure plus complexe qui nécessite le développement de nouvelles méthodes statistiques. Dans une première partie, je présenterai différentes problématiques liées à des statistiques d'occurrences de mots dans des génomes et décortiquerai plus en détail la question de savoir comment détecter si un mot a une fréquence d'apparition significativement anormale dans une séquence. Dans une deuxième partie, je présenterai différentes extensions pour tenir compte du fait qu'un motif d'ADN fonctionnel n'est pas toujours un « mot », mais qu'il ...

92C40 ; 62P10 ; 60J20 ; 92C42

... Lire [+]

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z