F Nous contacter

0

Documents  68R10 | enregistrements trouvés : 101

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


ISBN 978-0-8186-0644-1

Localisation : 1er étage/Congrès/PONT

algorithme # automatique # informatique # ordinateur

68-06 ; 68Q25 ; 68Q30 ; 68Q70 ; 68R10

... 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

- 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

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

DIMACS series in discrete mathematics and theoretical computer science , 0050

Localisation : Collection RdC

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


ISBN 978-0-471-81635-5

A wiley-interscience publication

Localisation : 1er étage/Congrès/KALA

algorithme # informatique theorique # theroie des graphes

68Qxx ; 68R10

... Lire [+]

V

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

Contemporary mathematics , 0588

Localisation : Collection RdC

combinatoires # arbres # hypergraphe # factorisation # algorithme

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

... Lire [+]

V

- 523 p.
ISBN 978-3-540-59175-7

Lecture notes in computer science , 0911

Localisation : Collection RdC

BDD et FDD # automate basculeur généralisé # automate fini probabiliste à 2 voies multitête # automaton cellulaire réversible # conception de structure de donnée géométrique # corps fini # graphe de Cayley # graphe de visibilité de polygône à 2 spirales # graphe récursif # génération aléatoire d'arbre coloré # informatique théorique # logique temporelle # machine Oracle monotone # machine de Turing # ordonnancement de chaîne de matrice # problème de Yekutieli et Mandelbrojt # programmation logique contrainte # réseau d'automate cyclique # séquence biologique BDD et FDD # automate basculeur généralisé # automate fini probabiliste à 2 voies multitête # automaton cellulaire réversible # conception de structure de donnée géométrique # corps fini # graphe de Cayley # graphe de visibilité de polygône à 2 spirales # graphe récursif # génération aléatoire d'arbre coloré # informatique théorique # logique temporelle # machine Oracle monotone # machine de Turing # ordonnancement de chaîne de matrice # ...

05Cxx ; 68Qxx ; 68R10

... Lire [+]

V


ISBN 978-0-444-89452-6

Annals of discrete mathematics , 0052

Localisation : 1er étage/Congrès/GAET

analyse combinatoire # combinatoire # geometrie # geometrie combinatoire # geometrie de l'informatique # geometrie discrete # graphes # mathematiques discretes # theorie des graphes

51N05 ; 68R05 ; 68R10 ; 68Rxx ; 68U05

... Lire [+]

V

Theoretical computer science , 0175

Localisation : 1er étage/Congrès/LYON

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

- 526 p.
ISBN 978-3-540-60723-6

Lecture notes in computer science , 1027

Localisation : Collection RdC

CABRI-graphe pour recherche et enseignement # CLAX compilateur visualisé # COMAIDE # GOVE # SWAN # Toscana # algorithme de tracé de graphe aléatoire # environnement de visualisation orienté grammaire # esthétique # moulle # optique # représentation de visibilité de graphe # système de management pour données conceptuelles # système de visualisation de structure de donnée # tracé de graphe orthogonal # visualisation d'information # visualisation de graphe 3-D intéractive rapide CABRI-graphe pour recherche et enseignement # CLAX compilateur visualisé # COMAIDE # GOVE # SWAN # Toscana # algorithme de tracé de graphe aléatoire # environnement de visualisation orienté grammaire # esthétique # moulle # optique # représentation de visibilité de graphe # système de management pour données conceptuelles # système de visualisation de structure de donnée # tracé de graphe orthogonal # visualisation d'information # visualisation ...

05Cxx ; 68R10 ; 90C35 ; 94C15

... Lire [+]

y


ISBN 978-981-3083-14-1

Localisation : 1er étage/Congrès/AUCK

algorithme # analyse combinatoire # complexité du calcul informatique # graphe # logique symbolique # mathématique discrète

05-06 ; 68Qxx ; 68R05 ; 68R10

... Lire [+]

V

- 209 p.
ISBN 978-0-8218-6597-2

DIMACS series in discrete mathematics and theoretical computer science , 0013

Localisation : Collection RdC

algorithme pour jeu stochastique simple # application de technique de théorie des jeux à la cryptograp # approximation diophantienne # complexité d'adaptation parallèle du théorème de Ramsey # composition de relation universelle # comptage approché avec circuit de profondeur constante unifo # factorisation d'entier et calcul de logarithme discret # jeu loyal contre adversaire tout-puissant # problème de E-isomorphisme # programme de branchement lu- seulement une fois # réduction aléatoire localement en théorie de la compléxité i # sécurité cryptographique parfaite partique # séparation forte de AC puissance 0 # théorème de la borne inférieure # thérorie de la complexité informatique algorithme pour jeu stochastique simple # application de technique de théorie des jeux à la cryptograp # approximation diophantienne # complexité d'adaptation parallèle du théorème de Ramsey # composition de relation universelle # comptage approché avec circuit de profondeur constante unifo # factorisation d'entier et calcul de logarithme discret # jeu loyal contre adversaire tout-puissant # problème de E-isomorphisme # programme de branchement ...

68P25 ; 68Q15 ; 68Q25 ; 68R05 ; 68R10

... Lire [+]

V

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

Lecture notes in computer science , 0324

Localisation : Collection RdC

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

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

Lecture notes in computer science , 1197

Localisation : Collection RdC

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

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

DIMACS series in discrete mathematics and theoretical computer science , 0053

Localisation : Collection RdC

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

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

Lecture notes in computer science , 1353

Localisation : Collection RdC

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

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

V

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

DIMACS series in discrete mathematics and theoretical computer science , 0046

Localisation : Collection RdC

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

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

Lecture notes in computer science , 1665

Localisation : Collection RdC

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

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z