In graph theory, the zig-zag product of regular graphs , denoted by , is a binary operation which takes a large graph and a small graph and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of .
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Produit zig-zag de graphes (fr)
- Зигзаг-произведение (ru)
- Zig-zag product (en)
|
| 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)
- In graph theory, the zig-zag product of regular graphs , denoted by , is a binary operation which takes a large graph and a small graph and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of . (en)
- В теории графов зигзаг-произведение регулярных графов (обозначается ) берёт большой граф и маленький граф и создаёт граф, примерно наследующий размер большого графа, но степень малого.Важным свойством зигзаг-произведения является то, что для хорошего экспандера распространение результирующего графа лишь слегка хуже распространения графа . Грубо говоря, зигзаг-произведение заменяет каждую вершину графа копией (облаком) графа и соединяет вершины, делая малый шаг (zig) внутри облака, а затем большой шаг (zag) между двумя облаками, и ещё один малый шаг внутри конечного облака. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
- In graph theory, the zig-zag product of regular graphs , denoted by , is a binary operation which takes a large graph and a small graph and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of . Roughly speaking, the zig-zag product replaces each vertex of with a copy (cloud) of , and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud. The zigzag product was introduced by . When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on, the zig-zag product was used in computational complexity theory to prove that symmetric logspace and logspace are equal. (en)
- В теории графов зигзаг-произведение регулярных графов (обозначается ) берёт большой граф и маленький граф и создаёт граф, примерно наследующий размер большого графа, но степень малого.Важным свойством зигзаг-произведения является то, что для хорошего экспандера распространение результирующего графа лишь слегка хуже распространения графа . Грубо говоря, зигзаг-произведение заменяет каждую вершину графа копией (облаком) графа и соединяет вершины, делая малый шаг (zig) внутри облака, а затем большой шаг (zag) между двумя облаками, и ещё один малый шаг внутри конечного облака. Зигзаг-произведение введено Рейнгольдом, Вадханом и Вигдерсоном. Зигзаг-произведение первоначально использовалось для явного конструирования экспандеров и экстракторов постоянной степени.Позднее зигзаг-произведение использовано в теории вычислительной сложности для доказательства равенства и . (ru)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is known for
of | |
| is known for
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)