Reconstructing a Tree Poset from Linear Extensions

Philippine Information Technology Journal

Fernandez, Jr., Proceso L.¹  Ordanel, Ivy D.¹ 

关键词: partial orders;    posets;    tree poset;    linear extensions;   

DOI  :  10.3860/pitj.v4i2.2734

学科分类：计算机科学（综合）

来源: Philippine Society of Information Technology Educators

【 摘 要 】

In Data Mining, one of the most relevant emerging problems is the generation of a network model from sequential data of events and observations. This can be abstracted by treating a sequence of observations as a linear order. The network model can then be generated by reconstructing a poset from the set of linear orders. There have already been algorithms devised to solve this problem, the most efficient of which runs in O(mn + n2)-time, where m is the number of linear orders and n is the number of elements in a linear order. However, if the class of poset is known, then it would also be relevant to find a more efficient algorithm to reconstruct it. This paper presents a more efficient algorithm that runs in O(mn)-time in reconstructing a tree poset from a given set of linear orders.

【 授权许可】

Unknown