In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets. In some applications of partition refinement, such as lexicographic breadth-first search, the data structure maintains as well an ordering on the sets in the partition.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Raffinement de partition (fr)
- Partition refinement (en)
- Уточнение разбиения (ru)
|
| rdfs:comment
| - In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets. In some applications of partition refinement, such as lexicographic breadth-first search, the data structure maintains as well an ordering on the sets in the partition. (en)
- En algorithmique, le raffinement de partition est une technique pour représenter une partition d'un ensemble comme une structure de données qui permet d'affiner cette partition en séparant chaque ensemble en plusieurs sous-ensembles. En ce sens, ce concept peut-être vu comme dual de la structure de données d'union-find, qui cherche à tenir à jour une partition en effectuant des opérations de fusion sur des couples d'ensembles. (fr)
- При разработке алгоритмов уточнение разбиения — это метод представления разбиения множества в виде структуры данных, которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно системе непересекающихся множеств, которая также поддерживает разбиение на непересекающиеся множества, но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как лексикографический поиск в ширину, структура данных поддерживает также порядок наборов в разделе. (ru)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - En algorithmique, le raffinement de partition est une technique pour représenter une partition d'un ensemble comme une structure de données qui permet d'affiner cette partition en séparant chaque ensemble en plusieurs sous-ensembles. En ce sens, ce concept peut-être vu comme dual de la structure de données d'union-find, qui cherche à tenir à jour une partition en effectuant des opérations de fusion sur des couples d'ensembles. Le raffinement de partition est un élément essentiel de plusieurs algorithmes efficaces en théorie des graphes ou en théorie des automates finis, tels que la minimisation des automates finis déterministes, l' pour le séquençage de tâches, ou le parcours en largeur lexicographique des graphes. (fr)
- In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also maintains a partition into disjoint sets but in which the operations merge pairs of sets. In some applications of partition refinement, such as lexicographic breadth-first search, the data structure maintains as well an ordering on the sets in the partition. Partition refinement forms a key component of several efficient algorithms on graphs and finite automata, including DFA minimization, the Coffman–Graham algorithm for parallel scheduling, and lexicographic breadth-first search of graphs. (en)
- При разработке алгоритмов уточнение разбиения — это метод представления разбиения множества в виде структуры данных, которая позволяет разбивать его множества на большее количество меньших множеств. В этом смысле уточнение разбиения двойственно системе непересекающихся множеств, которая также поддерживает разбиение на непересекающиеся множества, но в которой операции объединяют пары наборов. В некоторых приложениях уточнения разбиения, таких как лексикографический поиск в ширину, структура данных поддерживает также порядок наборов в разделе. Уточнение разбиения является ключевым компонентом нескольких эффективных алгоритмов на графах и конечных автоматах, включая минимизацию ДКА, для параллельного планирования и лексикографический поиск в ширину. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
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)