Partition refinement (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:wikiPageID | 31595644 (xsd:integer) |
| dbo:wikiPageLength | 11079 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1092943219 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Topological_sort dbr:Deterministic_finite_automaton dbr:Algorithm dbr:Doubly_linked_list dbr:Lexicographic_breadth-first_search dbr:Complement_(set_theory) dbr:Lexicographic_order dbr:Data_structure dbr:DFA_minimization dbr:Partition_of_a_set dbr:Graph_theory dbr:Intersection_(set_theory) dbr:Array_data_structure dbr:Chordal_graph dbr:Coffman–Graham_algorithm dbr:Collection_(abstract_data_type) dbr:Directed_acyclic_graph dbr:Disjoint-set_data_structure dbc:Data_structures dbr:Neighborhood_(graph_theory) dbr:Finite_automaton dbr:Disjoint_set dbr:Refinement_(sigma_algebra) |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Pipe |
| dcterms:subject | dbc:Data_structures |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:Structure105726345 yago:WikicatDataStructures |
| 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) |
| rdfs:label | Raffinement de partition (fr) Partition refinement (en) Уточнение разбиения (ru) |
| owl:sameAs | freebase:Partition refinement yago-res:Partition refinement wikidata:Partition refinement dbpedia-fr:Partition refinement dbpedia-ru:Partition refinement https://global.dbpedia.org/id/4tAxQ |
| prov:wasDerivedFrom | wikipedia-en:Partition_refinement?oldid=1092943219&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Partition_refinement |
| is dbo:wikiPageWikiLink of | dbr:Permutohedron dbr:Dynamic_connectivity dbr:Lexicographic_breadth-first_search dbr:List_of_partition_topics dbr:Weak_ordering dbr:Disjoint_sets dbr:DFA_minimization dbr:Partition_of_a_set dbr:Bisimulation dbr:Coffman–Graham_algorithm dbr:Cograph |
| is foaf:primaryTopic of | wikipedia-en:Partition_refinement |