Series-parallel partial order (original) (raw)
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series–parallel graphs. The comparability graphs of series-parallel partial orders are cographs.
| Property | Value |
|---|---|
| dbo:abstract | In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series–parallel graphs. The comparability graphs of series-parallel partial orders are cographs. Series-parallel partial orders have been applied in job shop scheduling, machine learning of event sequencing in time series data, transmission sequencing of multimedia data, and throughput maximization in dataflow programming. Series-parallel partial orders have also been called multitrees; however, that name is ambiguous: multitrees also refer to partial orders with no four-element diamond suborder and to other structures formed from multiple trees. (en) Последовательно-параллельный частичный порядок — это частично упорядоченное множество, построенное из меньших последовательно-параллельных частичных порядков с помощью двух простых операций соединения. Последовательно-параллельные частичные порядки можно описать как свободные от N-порядка конечные частичные порядки. Они имеют максимум два. Эти порядки включают и отношение достижимости в ориентированных деревьях и ориентированных параллельно-последовательных графах. Графы сравнимости последовательно-параллельных частичных порядков — это кографы. Последовательно-параллельные частичные порядки применяются в теории расписаний, машинном обучении последовательностей событий во временны́х рядах данных, последовательности передачи мультимедийных данных и максимизации пропускной способности в потоках данных. Последовательно-параллельные частичные порядки называются также мультидеревьями. Однако это название двусмысленно — также называют частичные порядки без четырёхэлементых подпорядков («алмазов») , а также другие структуры, образованные из нескольких деревьев. (ru) Послідовно-паралельний частковий порядок — це частково впорядкована множина, побудована з менших послідовно-паралельних часткових порядків за допомогою двох простих операцій з'єднання. Послідовно-паралельні часткові порядки можна описати як вільні від N-порядку скінченні часткові порядки. Вони мають максимум два. Ці порядки включають і відношення досяжності в орієнтованих деревах і орієнтованих паралельно-послідовних графах. Графи порівнянності послідовно-паралельних часткових порядків — це кографи. Послідовно-паралельні часткові порядки застосовують у теорії розкладів, машинному навчанні послідовностей подій у часових рядах даних, послідовності передачі мультимедійних даних і максимізації пропускної спроможності в потоках даних. Послідовно-паралельні часткові порядки називають також мультидеревами. Однак ця назва двозначна — також називають часткові порядки без чотириелементних підпорядків («алмазів»), а також інші структури, утворені з кількох дерев. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Series-parallel_partial_order.svg?width=300 |
| dbo:wikiPageID | 28826384 (xsd:integer) |
| dbo:wikiPageLength | 18038 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096699507 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Time_series dbr:Undirected_graph dbc:Order_theory dbr:Order_theory dbr:Orientation_(graph_theory) dbr:Multimedia dbr:NP-complete dbr:Lowest_common_ancestor dbr:Machine_learning dbr:Closure_(mathematics) dbr:Comparability_graph dbr:Computer_vision dbr:Parallel_computing dbr:Tree_(graph_theory) dbr:Dataflow_programming dbr:Hasse_diagram dbr:Linear_extension dbr:Separable_permutation dbr:Transitive_reduction dbr:Dataflow dbr:Fence_(mathematics) dbr:Partially_ordered_set dbr:Series_and_parallel_circuits dbr:Order_dimension dbr:Reachability dbr:Interval_graph dbr:Covering_relation dbc:Binary_relations dbr:Big_O_notation dbr:Cograph dbr:Directed_acyclic_graph dbr:Disjoint_union dbr:Planar_graph dbr:Sharp-P-complete dbr:Multitree dbr:Job_shop_scheduling dbr:Series–parallel_graph dbr:PQ_tree dbr:Associative_operation dbr:Series_parallel_graph dbr:Commutative_operation dbr:Expression_tree dbr:Weak_order dbr:File:Series-parallel_partial_order.svg |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Sub |
| dct:subject | dbc:Order_theory dbc:Binary_relations |
| rdfs:comment | In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series–parallel graphs. The comparability graphs of series-parallel partial orders are cographs. (en) Послідовно-паралельний частковий порядок — це частково впорядкована множина, побудована з менших послідовно-паралельних часткових порядків за допомогою двох простих операцій з'єднання. Послідовно-паралельні часткові порядки можна описати як вільні від N-порядку скінченні часткові порядки. Вони мають максимум два. Ці порядки включають і відношення досяжності в орієнтованих деревах і орієнтованих паралельно-послідовних графах. Графи порівнянності послідовно-паралельних часткових порядків — це кографи. (uk) Последовательно-параллельный частичный порядок — это частично упорядоченное множество, построенное из меньших последовательно-параллельных частичных порядков с помощью двух простых операций соединения. Последовательно-параллельные частичные порядки можно описать как свободные от N-порядка конечные частичные порядки. Они имеют максимум два. Эти порядки включают и отношение достижимости в ориентированных деревьях и ориентированных параллельно-последовательных графах. Графы сравнимости последовательно-параллельных частичных порядков — это кографы. (ru) |
| rdfs:label | Series-parallel partial order (en) Последовательно-параллельный частичный порядок (ru) Послідовно-паралельний частковий порядок (uk) |
| owl:sameAs | freebase:Series-parallel partial order wikidata:Series-parallel partial order dbpedia-ru:Series-parallel partial order dbpedia-uk:Series-parallel partial order https://global.dbpedia.org/id/4ufWV |
| prov:wasDerivedFrom | wikipedia-en:Series-parallel_partial_order?oldid=1096699507&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Series-parallel_partial_order.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Series-parallel_partial_order |
| is dbo:wikiPageDisambiguates of | dbr:Series-parallel |
| is dbo:wikiPageRedirects of | dbr:Series-parallel_order dbr:Series-parallel_poset |
| is dbo:wikiPageWikiLink of | dbr:1/3–2/3_conjecture dbr:Comparability_graph dbr:Weak_ordering dbr:Separable_permutation dbr:Fence_(mathematics) dbr:Partially_ordered_set dbr:Series_and_parallel_circuits dbr:Order_dimension dbr:Cograph dbr:Series-parallel dbr:Multitree dbr:Series–parallel_graph dbr:PQ_tree dbr:Series-parallel_order dbr:Series-parallel_poset |
| is foaf:primaryTopic of | wikipedia-en:Series-parallel_partial_order |
