| dbo:abstract
|
- In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and , who published its description in 1973. Although other algorithms for solving the clique problem have running times that are, in theory, better on inputs that have few maximal independent sets, the Bron–Kerbosch algorithm and subsequent improvements to it are frequently reported as being more efficient in practice than the alternatives. It is well-known and widely used in application areas of graph algorithms such as computational chemistry. A contemporaneous algorithm of , although presented in different terms, can be viewed as being the same as the Bron–Kerbosch algorithm, as it generates the same search tree. (en)
- 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éerlandais (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)
- Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик. (ru)
- Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 1973 року голландські математики Бронній і Кербош. Досі це один із найефективніших алгоритмів пошуку клік. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16104 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик. (ru)
- Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 1973 року голландські математики Бронній і Кербош. Досі це один із найефективніших алгоритмів пошуку клік. (uk)
- In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any additional vertices added to it while preserving its complete connectivity. The Bron–Kerbosch algorithm was designed by Dutch scientists Coenraad Bron and , who published its description in 1973. (en)
- 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éerlandais (en) et (en) qui en ont publié la description en 1973[réf. nécessaire]. (fr)
|
| rdfs:label
|
- Bron–Kerbosch algorithm (en)
- Algorithme de Bron-Kerbosch (fr)
- Алгоритм Брона — Кербоша (ru)
- Алгоритм Брона — Кербоша (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
