| dbo:abstract
|
- In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices. Frankl–Rödl graphs are named after Péter Frankl and Vojtěch Rödl, who proved in 1987 that (for certain ranges of the graph parameters) they have small independence number and high chromatic number. They have since become of interest to computational complexity theorists, as difficult examples for semidefinite programming based approximation algorithms for the vertex cover and graph coloring problems. Their properties with respect to these algorithms have been used to call into question the unique games conjecture. (en)
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. Les graphes de Frankl-Rödl portent le nom de Péter Frankl et Vojtěch Rödl, qui ont démontré en 1987 que, pour certaines valeurs des paramètres du graphe, ils ont un nombre de stabilité (taille du stable maximal) petit et un nombre chromatique élevé. Depuis, ces graphes sont devenus intéressants en complexité de calcul, comme des exemples qui sont difficiles pour la programmation semi-définie basée sur des algorithmes d'approximation du problème de couverture par sommets et pour les problèmes de coloration de graphes. Ses propriétés algorithmiques ont été utilisés pour remettre en question la conjecture des jeux uniques. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9377 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:caption
|
- The Frankl–Rödl graph consists of two copies of the 5-regular Clebsch graph. (en)
- The Frankl–Rödl graph consists of two copies of the cocktail party graph . (en)
|
| dbp:image
|
- 1 (xsd:integer)
- Clebsch graph.svg (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices. (en)
- En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents. (fr)
|
| rdfs:label
|
- Frankl–Rödl graph (en)
- Graphe de Frankl-Rödl (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
