Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Research School;Combinatorics;Computer Science
Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance) on some special classes of graphs such as cocomparability graphs.
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.
Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such ...
05C85 ; 68R10
... 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.
- 351 p.
ISBN 978-3-540-57879-6
Lecture notes in computer science , 0787
Localisation : Collection 1er étage
analyse de flux de données basée sur grammaire pour arrêter # arbre et algèbre en programmation # automate non déterministe # chemin coloré # grammaire de graphe # lambda-mu-calcul # langage d'arbre libre de contexte de sommet # ordonner des contraintes sur des arbres # programme de logique de contraintes # réseau de Pétri # schéma de programmes récursif du premier ordre # système de réécriture des termes à partage de constructeur # transducteur d'arbres
analyse de flux de données basée sur grammaire pour arrêter # arbre et algèbre en programmation # automate non déterministe # chemin coloré # grammaire de graphe # lambda-mu-calcul # langage d'arbre libre de contexte de sommet # ordonner des contraintes sur des arbres # programme de logique de contraintes # réseau de Pétri # schéma de programmes récursif du premier ordre # système de réécriture des termes à partage de constructeur # tr...
68P05 ; 68Q10 ; 68Qxx ; 68R10
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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 [+]
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.
- 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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Theoretical computer science , 0175
Localisation : Colloque 1er étage (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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 523 p.
ISBN 978-3-540-59175-7
Lecture notes in computer science , 0911
Localisation : Collection 1er étage
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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 403 p.
ISBN 978-3-540-10291-5
Lecture notes in computer science , 0100
Localisation : Collection 1er étage
graphes # informatique graphique # structure des données # traitement des données
68Pxx ; 68R10 ; 68Rxx
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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
68Q05 ; 68Q10 ; 68Q15 ; 68R10 ; 68Rxx
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 350 p.
ISBN 978-3-540-56402-7
Lecture notes in computer science , 0657
Localisation : Collection 1er étage
algorithme distribué # algorithme parallèle # combinatoire # concept de graphe théorique # décomposition de graphes # grammaire de graphe # géométrie
05Cxx ; 05Dxx ; 68R10 ; 68R15 ; 68S05
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
ISBN 978-0-471-81635-5
A wiley-interscience publication
Localisation : Colloque 1er étage (KALA)
algorithme # informatique theorique # theroie des graphes
68Qxx ; 68R10
... Lire [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
- 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 [+]
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
