m

Documents  68R10 | enregistrements trouvés : 105

O

-A +A

P Q

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.


ISBN 978-0-471-90490-8

Localisation : Colloque 1er étage (DUBL)

05-06 ; 49-06 ; 68R05 ; 68R10

... Lire [+]

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

- 486 p.
ISBN 978-0-12-386870-1

Perspectives in computing , 0015

Localisation : Colloque 1er étage (KYOT)

algorithme # co dage # code # complexite des algorithmes # cryptographie # mathematiques discretes # theorie de l' information

68Q25 ; 68Q30 ; 68R10 ; 94A60 ; 94Axx

... Lire [+]

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


ISBN 978-0-8186-0644-1

Localisation : Colloque 1er étage (PONT)

algorithme # automatique # informatique # ordinateur

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

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

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

- 306 p.
ISBN 978-3-540-16443-2

Lecture notes in computer science , 0214

Localisation : Collection 1er étage

arbre # grammaire # graphe # sémantique # syntaxe

68Q50 ; 68Q55 ; 68R10

... Lire [+]

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

- 474 p.
ISBN 978-3-540-16761-7

Lecture notes in computer science , 0226

Localisation : Collection 1er étage

algèbre linéaire numérique # analyse des algorithmes et complexité des problèmes # approximation # calcul par des appareils abstraits # logique et signification des programmes # logique mathématique et langage formels # théorie des graphes

68Q05 ; 68Q25 ; 68Q45 ; 68R10

... Lire [+]

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


ISBN 978-0-444-89360-4

Topics in discrete mathematics , 0001

Localisation : Colloque 1er étage (WASH)

analyse combinatoire # complexite # science de l'informatique # theorie des graphes

68Q15 ; 68R05 ; 68R10

... Lire [+]

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

- 719 p.
ISBN 978-3-540-55719-7

Lecture notes in computer science , 0623

Localisation : Collection 1er étage

algorithme de graphes # algorithme géométrique # analyse d'algorithme # automate fini # calcul parallèle # calcul symbolique # complexité de Kolmogorov # développement de programme # grammaire de graphes # langage # langage formel # logique # modèle # programmation # spécification de temps # sémantique concurrence # équivalence de processus

68Q10 ; 68Q25 ; 68Q30 ; 68Q50 ; 68R10

... Lire [+]

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


ISBN 978-0-444-89452-6

Annals of discrete mathematics , 0052

Localisation : Colloque 1er étage (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 [+]

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

- 403 p.
ISBN 978-3-540-56287-0

Lecture notes in computer science , 0652

Localisation : Collection 1er étage

algorithme # complexité # géométrie de l'informatique # logiciel # logique # programmation logique # spécification # sémantique

68N17 ; 68Q15 ; 68Q25 ; 68Q55 ; 68R10

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

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

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

DIMACS series in discrete mathematics and theoretical computer science , 0013

Localisation : Collection 1er étage

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

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

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

Lecture notes in computer science , 1027

Localisation : Collection 1er étage

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

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.

- 469 p.
ISBN 978-3-540-58950-1

Lecture notes in computer science , 0894

Localisation : Collection 1er étage

application et système # approche déclarative # contestation de tracé de graphe # démonstration de système # galerie de poster # géométrie # représentation de visibilité # tracé de proximité # tracé orthogonal # tracé planaire # tracé tri-dimensionnel # tracé vers le haut # traversée

05Cxx ; 68R10 ; 90C35 ; 94C15

... Lire [+]

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

- 657 p.
ISBN 978-0-8218-6609-2

DIMACS series in discrete mathematics and theoretical computer science , 0026

Localisation : Collection 1er étage

algorithme de l'informatique # clique # coloriage # fiabilité satisfaisante # informatique théorique # mathématique discrète # programmation combinatoire # programmation mathématique # théorie des graphes

68R10 ; 90C27

... Lire [+]

Z