m

F Nous contacter

0

Documents  68Q17 | enregistrements trouvés : 27

O

-A +A

P Q

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

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

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

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

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

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

- viii; 97 p.
ISBN 978-3-03719-069-2

Localisation : Colloque 1er étage (JENA)

informatique # optimisation

65-02 ; 65-03 ; 00B10 ; 01A70 ; 68-06 ; 90-06 ; 68Q17 ; 00B25

... Lire [+]

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

- x, 226 p.

Localisation : Séminaire 1er étage

théorie ergodique # géométrie # dynamique symbolique # combinatoire de mots # billard # transport de mesures # courbure de Ricci # flot quasi-conforme # variété Hadamard # isométrie # opérateur Lamé

37A35 ; 37C35 ; 11N37 ; 32G15 ; 32M15 ; 32Q45 ; 58J50 ; 35R30 ; 22E40 ; 20F65 ; 68Q17 ; 46Bxx ; 53DXX ; 53Cxx

... Lire [+]

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

- 224 p.
ISBN 978-0-8218-3483-1

Contemporary mathematics , 0349

Localisation : Collection 1er étage

théorie des groupes # groupe de permutation # groupe non-abélien # théorie quantique # informatique # algorithme # groupe d'automorphisme # calcul quantique

20B40 ; 20E05 ; 20F28 ; 81P68 ; 68Q05 ; 68Q17 ; 68Q42 ; 68Q45 ; 68T05

... Lire [+]

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

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

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

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

Research schools;Combinatorics;Computer Science;Topology

68Q17 ; 57Q35

... Lire [+]

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

Research talks;Computer Science

Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - property testing
Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - ...

68Q15 ; 68Q17 ; 68Q19 ; 68W20 ; 68W25

... Lire [+]

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

- xi; 339 p.
ISBN 978-1-107-19923-1

Cambridge studies in advanced mathematics , 0169

Localisation : Ouvrage RdC (LAND)

complexité de calcul # géométrie algébrique # multiplication matricielle # hypothèse de Valiant

68-02 ; 14-02 ; 14Q20 ; 68Q17 ; 68Q25 ; 68W30

... Lire [+]

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

- xviii; 691 p.
ISBN 978-3-03719-139-2

Tracts in mathematics , 0022

Localisation : Ouvrage RdC (FOUN)

groupe fini # groupe infini # analyse combinatoire énumérative # semigroupe # groupoïde # algèbre homologique # groupe de permutation # groupe de réflexion # groupe de Coxeter # monoïde # catégorie # décomposition # groupe de Garside # conjugaison # groupe de tresses # groupe de Artin-Tits # variété de Deligne-Luzstig # groupe ordonné # équation de Yang-Baxter

20Fxx ; 20F05 ; 20F10 ; 20F36 ; 20F60 ; 20F65 ; 20M05 ; 20M10 ; 05A05 ; 18B40 ; 18G35 ; 20B30 ; 20F55 ; 20L05 ; 20M50 ; 20N02 ; 68Q17

... Lire [+]

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

- xiii; 228 p.
ISBN 978-0-691-16352-9

Localisation : Loisir RdC

problème du voyageur de commerce # programmation # optimisation # complexité de calcul

00A09 ; 90-01 ; 90C60 ; 68Q17

... Lire [+]

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

- xii; 153 p.
ISBN 978-1-4939-0747-2

SpringerBriefs in mathematics

Localisation : Ouvrage RdC (LOHR)

informatique théorique # théorie combinatoire des groupes # compression de données # programmation

20F10 ; 20M05 ; 68Q17 ; 68Q42 ; 68-02 ; 68Q25 ; 68Q70

... Lire [+]

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

- xviii; 586 p.
ISBN 978-3-03719-116-3

Tracts in mathematics , 0018

Localisation : Ouvrage RdC (NOVA)

analyse numérqiue # algorithme # approximation de fonctions multivariées # espace de Hilbert # approximation multivariée # problème linéaire # problème quasi-linéaire # équation de Poisson # tractabilité

65-02 ; 65Y20 ; 68Q17 ; 68Q25 ; 41A63 ; 46E22 ; 28C20 ; 46E30 ; 65N99 ; 65R20 ; 65D15

... Lire [+]

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

- viii; 106 p.
ISBN 978-3-03719-107-1

EMS series of lectures in mathematics

Localisation : Ouvrage RdC (TRIE)

base de Haar # base faber # espace de fonction pondéré # ondelettes

46-02 ; 46E35 ; 42C40 ; 42B35 ; 68Q17 ; 41A55

... Lire [+]

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

- xv; 617 p.
ISBN 978-3-642-24507-7

Algorithms and combinatorics , 0027

Localisation : Ouvrage RdC (JUKN)

complexité de calcul # fonction booléenne # circuit de communication # analyse combinatoire

68R05 ; 68Q17 ; 94C10

... Lire [+]

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

- xx; 439 p.
ISBN 978-0-8218-6907-9

Graduate studies in mathematics , 0128

Localisation : Collection 1er étage

algèbre multilinéaire # produit tenseur # matrice # théorie du signal # phylogénétique # statistiques algébriques # G-variétés # théorème d'Alexander-Hirschowitz # méthode de Weyman-Kempf

15-01 ; 15A69 ; 68Q17 ; 14M17 ; 94A12 ; 94A13 ; 20G05 ; 62E10 ; 14N05 ; 14M12 ; 14M15 ; 15A72 ; 15A75

... Lire [+]

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

- xvi; 247 p.
ISBN 978-0-521-15433-8

London mathematical society lecture note series , 0382

Localisation : Collection 1er étage

complexité # variable aléatoire # analyse mathématique # limite arithmétique # mesure de Loeb # arbre de décision

03F20 ; 03-02 ; 03C62 ; 03F30 ; 68Q17

... Lire [+]

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

- xviii; 657 p.
ISBN 978-3-03719-084-5

Tracts in mathematics , 0012

Localisation : Ouvrage RdC (NOVA)

analyse multivariée # algorithme

65Y20 ; 68Q17 ; 68Q25 ; 41A63 ; 65-02 ; 46E22 ; 28C20 ; 46E30 ; 11K38 ; 65D32

... Lire [+]

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

- ix; 296 p.
ISBN 978-3-03719-085-2

Tracts in mathematics , 0011

Localisation : Ouvrage RdC (TRIE)

espace fonctionnel # bases # espace de Sobolev # système de faber # echantillonage # approximation multidimensionel # intégration numérique # discrépance

46-02 ; 46E35 ; 42C40 ; 42B35 ; 68Q17 ; 41A55 ; 46B15 ; 42C15 ; 41A63 ; 41A30 ; 65D30

... Lire [+]

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

- x; 114 p.
ISBN 978-0-8218-5192-0

University lecture series , 0055

Localisation : Collection 1er étage

complexité de calcul # générateur de nombres aléatoires # théorie de l'information algorithmique # algorithme randomisé # pseudo-aléatoire

68-01 ; 68-02 ; 68R01 ; 68Q15 ; 68Q17 ; 68W20 ; 68Q30

... Lire [+]

Z