Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Post-edited  Le problème Graph Motif - Partie 1
Fertin, Guillaume (Auteur de la Conférence) | CIRM (Editeur )

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterization by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem. Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit ...

05C62 ; 05C85 ; 68R10

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Le problème Graph Motif - Partie 2
Fertin, Guillaume (Auteur de la Conférence) | CIRM (Editeur )

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multi angle  Embedding extension problems
Mohar, Bojan (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Consider a sample of points drawn from some unknown density on $R^d$. Assume the only information we have about the sample are the $k$-nearest neighbor relationships: we know who is among the $k$-nearest neighors of whom, but we do not know any distances between points, nor the point coordinates themselves. We prove that as the sample size goes to infinty, it is possible to reconstruct the underlying density p and the distances of the points (up to a multiplicative constant).

$k$-nearest neighbor graph - random geometric graph - ordinal embedding
Consider a sample of points drawn from some unknown density on $R^d$. Assume the only information we have about the sample are the $k$-nearest neighbor relationships: we know who is among the $k$-nearest neighors of whom, but we do not know any distances between points, nor the point coordinates themselves. We prove that as the sample size goes to infinty, it is possible to reconstruct the underlying density p and the distances of the points (up ...

62G07 ; 62G30 ; 68R10

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki from 1993, a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov's systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions.
Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length $O(g^{3/2}n^{1/2})$ for any triangulated combinatorial surface of genus g with n triangles, and describe an $O(gn)$-time algorithm to compute such a decomposition.
Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.
systolic geometry - computational topology - topological graph theory - graphs on surfaces - triangulations - random graphs
How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed ...

05C10 ; 68U05 ; 53C23 ; 57M15 ; 68R10

Filtrer

Type
Domaine
Codes MSC

Z