About: Expander graph

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Expander graph Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Unit108189659, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FExpander_graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Attributes	Values
rdf:type	software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659
rdfs:label	Expander (graf) (cs) Expander-Graph (de) Expander graph (en) Taux d'expansion (théorie des graphes) (fr) Ekspander (pl) Экспандер (теория графов) (ru) Збільшувач (теорія графів) (uk) 扩展图 (zh)
rdfs:comment	Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde \|V'\| ≥ (1+ε) \|V\| (cs) In der Mathematik sind Expander-Graphen Familien von Graphen, die gleichzeitig dünn und hochzusammenhängend sind und sehr gute Stabilitätseigenschaften haben, sich also nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen lassen. Anschaulich heißt das, dass jede „kleine“ Teilmenge von Knoten eine relativ „große“ Nachbarschaft hat. (de) In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes. (en) En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique. (fr) Ekspander – graf o niewielkiej liczbie krawędzi, w którym każdy podzbiór wierzchołków ma dużo sąsiadów. Istnieje kilka nierównoważnych formalizacji tej własności, definiujących różne klasy ekspanderów. Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki: dowodów w teorii złożoności, projektowaniu sieci sortujących, kodów korekcji błędów, ekstraktorów losowości i odpornych na błędy schematów komunikacji w sieciach komputerowych. (pl) Экспандер (от англ. expander graph — расширяющий граф) — разреженный граф, при этом связность может определяться по вершинам, дугам или спектру (смотрите ниже). (ru) 在组合数学中，扩展图（英語：Expander graph）是一种具有强连通性质的，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。 (zh) Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче). (uk)
dcterms:subject	Graph families
Wikipage page ID	9313 (xsd:integer)
Wikipage revision ID	1121114256 (xsd:integer)
Link from a Wikipage to another Wikipage	Cambridge University Press Multigraph Algebraic connectivity Algorithm Graph families Hypercube graph Peter Sarnak Regular graph Vitali Milman Degree (graph theory) Derandomization Independent set (graph theory) Pseudorandom generator Complete graph Computer network Connectivity (graph theory) Cryptography SL (complexity) Orthogonal Symmetric matrix Salil Vadhan Eigenvalue Eigenvector Graph coloring Boundary (graph theory) Erdős–Rényi model L (complexity) Zig-zag product Linear algebra Component (graph theory) Computational complexity theory Computer science PCP theorem Superstrong approximation Avi Wigderson Additive combinatorics Hash function Laplacian matrix Spectral graph theory Stationary distribution Adjacency matrix Alexander Lubotzky Alon-Boppana bound American Mathematical Society Edge (graph theory) Noga Alon Cayley graph Cheeger bound Cheeger constant Directed graph Graph theory Journal of the ACM Rayleigh quotient Riemannian geometry ACM SIGACT News Abstract algebra Cheeger constant (graph theory) Chernoff bound Bipartite graph Distance (graph theory) Markov chains Sorting network Spectral theorem Omer Reingold Ramanujan graph Vertex (graph theory) Expander code Expander mixing lemma Extractor (mathematics) Extremal graph theory

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 39 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software