| Property |
Value |
| dbo:abstract
|
- En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de nœuds est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale).L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néérlandais (en) et (en) qui en ont publié la description en 1973[réf. nécessaire]. Bien que d'autres algorithmes aient en théorie de meilleures complexités pour résoudre le problème de la clique maximale sur des entrées qui ont un petit nombre d'ensembles indépendants, l'algorithme de Bron–Kerbosch (et ses améliorations) se révèlent souvent plus efficaces en pratique.C'est une des raisons qui font que cet algorithme est très populaire dans des domaines d'application tels que la chimie numérique. Un algorithme contemporain d'Akkoyunlu peut être considéré comme identique à l'algorithme de Bron–Kerbosch, quoique formulé différemment, car il génère le même arbre de recherche. (fr)
- En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de nœuds est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale).L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néérlandais (en) et (en) qui en ont publié la description en 1973[réf. nécessaire]. Bien que d'autres algorithmes aient en théorie de meilleures complexités pour résoudre le problème de la clique maximale sur des entrées qui ont un petit nombre d'ensembles indépendants, l'algorithme de Bron–Kerbosch (et ses améliorations) se révèlent souvent plus efficaces en pratique.C'est une des raisons qui font que cet algorithme est très populaire dans des domaines d'application tels que la chimie numérique. Un algorithme contemporain d'Akkoyunlu peut être considéré comme identique à l'algorithme de Bron–Kerbosch, quoique formulé différemment, car il génère le même arbre de recherche. (fr)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17303 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1965 (xsd:integer)
- 1973 (xsd:integer)
- 1976 (xsd:integer)
- 2001 (xsd:integer)
- 2004 (xsd:integer)
- 2006 (xsd:integer)
- 2008 (xsd:integer)
- 2010 (xsd:integer)
- 2013 (xsd:integer)
|
| prop-fr:art
|
- Bron-Kerbosch algorithm (fr)
- Bron-Kerbosch algorithm (fr)
|
| prop-fr:arxiv
|
- 1006.544000 (xsd:double)
- 1103.031800 (xsd:double)
|
| prop-fr:bibcode
| |
| prop-fr:contribution
|
- Substructure and maximal common substructure searching (fr)
- Listing all maximal cliques in sparse graphs in near-optimal time (fr)
- Substructure and maximal common substructure searching (fr)
- Listing all maximal cliques in sparse graphs in near-optimal time (fr)
|
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.113700 (xsd:double)
- 10.114500 (xsd:double)
|
| prop-fr:editor1First
|
- Otfried (fr)
- Otfried (fr)
|
| prop-fr:editor1Last
| |
| prop-fr:editor2First
|
- Kyung-Yong (fr)
- Kyung-Yong (fr)
|
| prop-fr:editor2Last
| |
| prop-fr:editor3First
| |
| prop-fr:editor3Last
| |
| prop-fr:editorFirst
|
- Patrick (fr)
- Patrick (fr)
|
| prop-fr:editorLast
|
- Bultinck (fr)
- Bultinck (fr)
|
| prop-fr:isbn
| |
| prop-fr:journal
|
- Theoretical Computer Science (fr)
- Commun. ACM (fr)
- International Journal of Parallel Programming (fr)
- Israel J. Math. (fr)
- SIAM Journal on Computing (fr)
- Theoretical Computer Science (fr)
- Commun. ACM (fr)
- International Journal of Parallel Programming (fr)
- Israel J. Math. (fr)
- SIAM Journal on Computing (fr)
|
| prop-fr:lang
| |
| prop-fr:lienAuteur
|
- David Eppstein (fr)
- Leo Moser (fr)
- David Eppstein (fr)
- Leo Moser (fr)
|
| prop-fr:mr
| |
| prop-fr:nom
|
- Bron (fr)
- Tomita (fr)
- Chen (fr)
- Moon (fr)
- Johnston (fr)
- Tanaka (fr)
- Cazals (fr)
- Löffler (fr)
- Koch (fr)
- Moser (fr)
- Akkoyunlu (fr)
- Eppstein (fr)
- Karande (fr)
- Kerbosch (fr)
- Strash (fr)
- Takahashi (fr)
- Bron (fr)
- Tomita (fr)
- Chen (fr)
- Moon (fr)
- Johnston (fr)
- Tanaka (fr)
- Cazals (fr)
- Löffler (fr)
- Koch (fr)
- Moser (fr)
- Akkoyunlu (fr)
- Eppstein (fr)
- Karande (fr)
- Kerbosch (fr)
- Strash (fr)
- Takahashi (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 3 (xsd:integer)
- 9 (xsd:integer)
|
| prop-fr:pages
|
- 1 (xsd:integer)
- 23 (xsd:integer)
- 28 (xsd:integer)
- 209 (xsd:integer)
- 403 (xsd:integer)
- 483 (xsd:integer)
- 564 (xsd:integer)
- 575 (xsd:integer)
|
| prop-fr:prénom
|
- Akira (fr)
- L. (fr)
- C. (fr)
- David (fr)
- E. A. (fr)
- Maarten (fr)
- F. (fr)
- J. W. (fr)
- Coenraad (fr)
- Darren (fr)
- Etsuji (fr)
- H. C. (fr)
- Haruhisa (fr)
- Ina (fr)
- Joep (fr)
- Lingran (fr)
- Akira (fr)
- L. (fr)
- C. (fr)
- David (fr)
- E. A. (fr)
- Maarten (fr)
- F. (fr)
- J. W. (fr)
- Coenraad (fr)
- Darren (fr)
- Etsuji (fr)
- H. C. (fr)
- Haruhisa (fr)
- Ina (fr)
- Joep (fr)
- Lingran (fr)
|
| prop-fr:périodique
|
- Journal of Experimental Algorithmics (fr)
- Lecture Notes in Computer Science (fr)
- Journal of Experimental Algorithmics (fr)
- Lecture Notes in Computer Science (fr)
|
| prop-fr:titre
|
- 21 (xsd:integer)
- Listing all maximal cliques in large sparse real-world graphs (fr)
- Cliques of a graph—variations on the Bron–Kerbosch algorithm (fr)
- The worst-case time complexity for generating all maximal cliques and computational experiments (fr)
- A note on the problem of reporting maximal cliques (fr)
- On cliques in graphs (fr)
- The enumeration of maximal cliques of large graphs (fr)
- Enumerating all connected maximal common subgraphs in two graphs (fr)
- Computational Medicinal Chemistry for Drug Discovery (fr)
- Algorithm 457: finding all cliques of an undirected graph (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 2 (xsd:integer)
- 3 (xsd:integer)
- 5 (xsd:integer)
- 16 (xsd:integer)
- 250 (xsd:integer)
- 363 (xsd:integer)
- 407 (xsd:integer)
- 6506 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer-Verlag (fr)
- ACM (fr)
- CRC Press (fr)
- Springer-Verlag (fr)
- ACM (fr)
- CRC Press (fr)
|
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de nœuds est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale).L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néérlandais (en) et (en) qui en ont publié la description en 1973[réf. nécessaire]. (fr)
- En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté. Autrement dit, l'algorithme liste tous les sous-ensembles de sommets dans lesquels tout couple de nœuds est connecté par un lien (c'est une clique), et aucun des ensembles de sommets listés ne peut être étendu en conservant cette propriété (la clique est maximale).L'algorithme de Bron–Kerbosch a été conçu par les scientifiques néérlandais (en) et (en) qui en ont publié la description en 1973[réf. nécessaire]. (fr)
|
| rdfs:label
|
- Algorithme de Bron-Kerbosch (fr)
- Bron–Kerbosch algorithm (en)
- Алгоритм Брона — Кербоша (ru)
- Алгоритм Брона — Кербоша (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
