F Nous contacter

0

Documents  68R10 | enregistrements trouvés : 102

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 RdC

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 [+]

V

- xi; 556 p.
ISBN 978-2-85629-371-3

Astérisque , 0352

Localisation : Périodique 1er étage

Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces homogènes # espaces métriques # espaces normés # espaces perfectoïdes # existence globale # fibré de Higgs # fibré holomorphe plat # forme quartique binaire # formule de KPZ # gravité quantique # groupe de Galois motivique # groupe de Selmer # groupes de Lie # groupes quasi-fuchsiens # hamiltonien # marches aléatoires # mélange exponentiel du fibré des repères # mesures de Liouville # mesures stationnaires # métrique harmonique # modération topologique # monodromie-poids # motifs de Tate mixtes # multizêtas # nonlinéaire # norme d'uniformité # orbites coadjointes # plongement métrique # principe de transfert # programmation semi-définie # Programme de Ribe # progression arithmétique # pureté # rang # réarrangement # Relativité générale # représentations des groupes algébriques réductifs # représentations des groupes de Lie compacts # résonances en espace temps # rigidité # singularités irrégulières # stabilité orbitale # surfaces enfermées # système stellaire auto-gravitant # théorème de Lefschetz difficile # théorie de Hodge # théorie géométrique des invariants # topologie étale # trous noirs # types stablement dominés # variétés de drapeaux # variétés hyperboliques de dimension 3 # Vlasov-Poisson Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces ...

14L24 ; 14M15 ; 20G05 ; 22E46 ; 35-XX ; 35Qxx ; 37-XX ; 37NXX ; 37N20 ; 82-XX ; 82Cxx ; 85-XX ; 85AXX ; 05C12 ; 05C85 ; 46N10 ; 68Q17 ; 68R10 ; 68W25 ; 90C22 ; 91B14 ; 11G99 ; 11G05 ; 11E76 ; 14J60 ; 32C38 ; 53C07 ; 83C57 ; 83C75 ; 83C05 ; 35L67 ; 60C05 ; 60F17 ; 60-02 ; 05C10 ; 05C80 ; 82B20 ; 82B05 ; 82B27 ; 35B34 ; 35E20 ; 35B60 ; 35Q60 ; 35Q35 ; 11N13 ; 11B25 ; 30F99 ; 03C64 ; 03C65 ; 03C99 ; 14G22 ; 11G25 ; 14F20 ; 14G20 ; 22E40 ; 37D40 ; 60B99

... Lire [+]

V

- xiii; 240 p.
ISBN 978-0-8218-9038-7

Contemporary mathematics , 0588

Localisation : Collection 1er étage

combinatoires # arbres # hypergraphe # factorisation # algorithme

05C85 ; 68W05 ; 68W10 ; 68R05 ; 68R10 ; 05C05 ; 05C65 ; 05-06 ; 05C70 ; 00B25

... Lire [+]

V

- viii; 260 p.
ISBN 978-3-642-15013-5

Mathematics and visualization

Localisation : Colloque RdC

théorie des graphes # topologie

57Q05 ; 68U05 ; 68U20 ; 00B25 ; 00A69 ; 05C90 ; 68R10 ; 54H99

... Lire [+]

V

- xiv; 370 p.
ISBN 978-0-8218-4380-2

DIMACS series in discrete mathematics and theoretical computer science , 0069

Localisation : Collection 1er étage

combinatoires # informatique # chimie # graphe

68R10 ; 68T05 ; 68T35 ; 05C35 ; 05C30 ; 05C62 ; 05-06 ; 68-06 ; 00B25

... Lire [+]

V

- xiii, 705 p.
ISBN 978-0-8218-4471-7

Proceedings of symposia in pure mathematics , 0077

Localisation : Collection 1er étage

théorie des graphes # série Dirichlet # fonction zéta # fractals # EDP # théorie des opérateurs # analyse globale # variété # analyse combinatoire # contrôle des systèmes mécaniques # théorie quantique

05C90 ; 11M41 ; 20F65 ; 28A80 ; 35-XX ; 47-XX ; 58-XX ; 68R10 ; 70Q05 ; 78AXX ; 81-XX

... Lire [+]

V

- 416 p.

graphe # ordinateur # coloration de graphe # théorème de Menger # problème de Zarenkiewicz # sciences sociales # perte # circuit d'Hamilton

05-06 ; 05Cxx ; 68R10

... Lire [+]

V

- 193 p.
ISBN 978-0-8218-3551-7

DIMACS series in discrete mathematics and theorerical computer science , 0063

Localisation : Collection 1er étage

théorie graphe # morphisme # physique statistique # percolation # graphe aléatoire # modèle à forte contrainte # phase de transition # combinatoire # homomorphisme

05-06 ; 05A16 ; 05C15 ; 05C60 ; 60-06 ; 60J10 ; 60K35 ; 68R10 ; 82B20

... Lire [+]

V

- 167 p.
ISBN 978-0-8218-1546-5

DIMACS series in discrete mathematics and theoretical computer science , 0053

Localisation : Collection 1er étage

nformatique # réseau informatique # combinatoire # réseau de communication # organisation des systèmes informatiques # construction de réseau

68-06 ; 68M10 ; 68M15 ; 68R05 ; 68R10 ; 68M14 ; 68W10 ; 68W15 ; 68W20

... Lire [+]

V

- 171 p.
ISBN 978-0-8218-2141-1

Contemporary mathematics , 0275

Localisation : Collection 1er étage

approximation numérique # théorie des opérateurs # application # analyse numérique # combinatoire # théorie des graphes # orthogonalisation # théorie des corps de classes # application du processus de Markov # théorie des files d'attente # évaluation de performance

35F05 ; 47N40 ; 68R10 ; 65F25 ; 11R37 ; 60K20 ; 60K25 ; 68M20 ; 00A30 ; 68R05

... Lire [+]

V

- 370 p.
ISBN 978-3-540-64824-6

Lecture notes in computer science , 1449

Localisation : Collection 1er étage

algorithme # analyse d"algorithme # combinatoire # complexité calculatoire # cryptographie # géométrie calculatoire # informatique # processus distribué # processus parallèle # reseau commuté # structure de données # théorie des graphes

05-06 ; 68-06 ; 68Q25 ; 68R10

... Lire [+]

V

- 306 p.
ISBN 978-0-8218-1184-9

DIMACS series in discrete mathematics and theoretical computer science , 0050

Localisation : Collection 1er étage

algorithme de calcul # algorithme numérique # algorithmique # algèbre numérique # calcul des algorithmes numériques # calcul parallèle # complexité des algorithmes # gestion de mémoire # infographie # informatique théorique # mathématique discrète # modèle de calcul # structure des données # traitement des données

65Fxx ; 65Y20 ; 68Pxx ; 68Q05 ; 68Q25 ; 68R01 ; 68R10 ; 68U05 ; 68W01 ; 68W40

... Lire [+]

V

- 414 p.
ISBN 978-3-540-66731-5

Lecture notes in computer science , 1665

Localisation : Collection 1er étage

algorithme # classe de complexité # complexité des algorithmes # géométrie de l informatique # informatique théorique # logique et spécification de programme # logique mathématique # mathématique discrète # mode de calcul # strucutre de données # théorie des graphes

00B25 ; 05-06 ; 68-06 ; 68R10

... Lire [+]

V

Theoretical computer science , 0175

Localisation : Colloque RdC

algorithme # algorithme parallèle # application # architecture # encodage # fonction booléenne # graphe # informatique théorique # problème d'interval # reconnaissance # structure et représentation de treillis # treillis booléens

68Q10 ; 68Q20 ; 68Q30 ; 68R10 ; 68Rxx ; 68T10

... Lire [+]

V

- 249 p.
ISBN 978-0-8218-1004-0

DIMACS series in discrete mathematics and theoretical computer science , 0046

Localisation : Collection 1er étage

algorithmique # classe de complexité # communication optique # complexité # informatique théorique # mathématique économique # mathématiques discrètes # optimisation combinatoire # programmation mathématique # programmation non linéaire # recherche opérationnelle # réécriture de système # théorie de la décision

03B05 ; 68Q25 ; 68Q42 ; 68R10 ; 68T01 ; 68T15 ; 90A05 ; 90B40 ; 90C27 ; 90C30

... Lire [+]

V

- 562 p.
ISBN 978-3-540-50110-7

Lecture notes in computer science , 0324

Localisation : Collection 1er étage

caractéristique sémantique # construction de langage # langage de programmation # langage formel # logique de programmation # logique mathématiques # mathématiques discrètes # théorie des graphes

68N15 ; 68N17 ; 68Q35 ; 68Q45 ; 68R10 ; 68Rxx

... Lire [+]

V

- 448 p.
ISBN 978-3-540-63938-1

Lecture notes in computer science , 1353

Localisation : Collection 1er étage

algorithme non numérique # conception de graphe # conception de logiciel # géométrie de l'informatique # informatique graphique # mathématique discrète # modélisation d'objet # théorie des graphes

68R10 ; 68U05

... Lire [+]

V

- 406 p.
ISBN 978-3-540-62559-9

Lecture notes in computer science , 1197

Localisation : Collection 1er étage

analyse d'algorithme # calcul informatique # classe de complexité # concept de graphe théorique # géométrie de l'informatique # informatique théorique # langage formel # logique et signification de programme # logique mathématique # mathématique discrète # mode de calcul # modélisation d'objet # problème de complexité # structure des données # théorie des graphes analyse d'algorithme # calcul informatique # classe de complexité # concept de graphe théorique # géométrie de l'informatique # informatique théorique # langage formel # logique et signification de programme # logique mathématique # mathématique discrète # mode de calcul # modélisation d'objet # problème de complexité # structure des données # théorie des graphes

68Q05 ; 68Q10 ; 68Q15 ; 68R10 ; 68Rxx

... Lire [+]

V

- 408 p.
ISBN 978-3-540-62495-0

Lecture notes in computer science , 1190

Localisation : Collection 1er étage

aide et conception assistée de système # algorithme non numérique # analyse des algorithmes # application de la théorie des graphes # circuit réseau # combinatoire # graphe informatique # géométrie de l'informatique # ingineering des logiciels # logiciel # mathématique discrète # modélisation d'objet # outil et technique # problème # problème de complexité # programmation mathématique # théorie des graphes aide et conception assistée de système # algorithme non numérique # analyse des algorithmes # application de la théorie des graphes # circuit réseau # combinatoire # graphe informatique # géométrie de l'informatique # ingineering des logiciels # logiciel # mathématique discrète # modélisation d'objet # outil et technique # problème # problème de complexité # programmation mathématique # théorie des graphes

05Cxx ; 68R10 ; 68U05 ; 68Uxx ; 90C35

... Lire [+]

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z