| Property |
Value |
| dbo:abstract
|
- En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes et , noté , prend en arguments un grand graphe et un petit graphe et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si est un bon graphe expanseur, alors le taux d'expansion du graphe résultat est seulement un peu moins bon que le taux d'expansion de . De manière informelle, le produit zig-zag remplace chaque sommet de par une copie de (un « nuage », cloud en anglais) et relie les sommets en trois étapes : une première (le zig) à l'intérieur du nuage, suivi d'une deuxième entre deux nuages, et enfin une troisième (le zag) à l'intérieur du nuage d'arrivée. Le produit zig-zag a été introduit par Omer Reingold, Salil Vadhan et Avi Wigderson en 2002 et a été utilisé pour la construction explicite d'expanseurs et d'extracteurs de degré constant. Les auteurs ont obtenu le prix Gödel pour ce travail. Ultérieurement le produit zig-zag a été employé en théorie de complexité pour prouver que les classes de complexité SL (espace logarithmique symétrique) et L (espace logarithmique) coïncident. (fr)
- En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes et , noté , prend en arguments un grand graphe et un petit graphe et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si est un bon graphe expanseur, alors le taux d'expansion du graphe résultat est seulement un peu moins bon que le taux d'expansion de . De manière informelle, le produit zig-zag remplace chaque sommet de par une copie de (un « nuage », cloud en anglais) et relie les sommets en trois étapes : une première (le zig) à l'intérieur du nuage, suivi d'une deuxième entre deux nuages, et enfin une troisième (le zag) à l'intérieur du nuage d'arrivée. Le produit zig-zag a été introduit par Omer Reingold, Salil Vadhan et Avi Wigderson en 2002 et a été utilisé pour la construction explicite d'expanseurs et d'extracteurs de degré constant. Les auteurs ont obtenu le prix Gödel pour ce travail. Ultérieurement le produit zig-zag a été employé en théorie de complexité pour prouver que les classes de complexité SL (espace logarithmique symétrique) et L (espace logarithmique) coïncident. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13020 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
| |
| prop-fr:art
|
- rotation map (fr)
- zig-zag product (fr)
- rotation map (fr)
- zig-zag product (fr)
|
| prop-fr:auteur
| |
| prop-fr:doi
| |
| prop-fr:id
|
- 490372153 (xsd:integer)
- 508877209 (xsd:integer)
|
| prop-fr:lang
| |
| prop-fr:nom
|
- Reingold (fr)
- Vadhan (fr)
- Reingold (fr)
- Vadhan (fr)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- Omer (fr)
- Salil (fr)
- Omer (fr)
- Salil (fr)
|
| prop-fr:titreChapitre
|
- Pseudorandom walks on regular digraphs and the RL vs. L problem (fr)
- Pseudorandom walks on regular digraphs and the RL vs. L problem (fr)
|
| prop-fr:titreOuvrage
|
- Proc. 38th ACM Symposium on Theory of Computing Proc. (fr)
- Proc. 38th ACM Symposium on Theory of Computing Proc. (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes et , noté , prend en arguments un grand graphe et un petit graphe et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si est un bon graphe expanseur, alors le taux d'expansion du graphe résultat est seulement un peu moins bon que le taux d'expansion de . (fr)
- En théorie des graphes, le produit zig-zag de graphes est une opération sur des graphes réguliers. Le produit de deux graphes et , noté , prend en arguments un grand graphe et un petit graphe et produit un graphe qui hérite approximativement de la taille du grand graphe et du degré du petit. Une propriété importante du produit zig-zag est que si est un bon graphe expanseur, alors le taux d'expansion du graphe résultat est seulement un peu moins bon que le taux d'expansion de . (fr)
|
| rdfs:label
|
- Produit zig-zag de graphes (fr)
- Produit zig-zag de graphes (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
