DocumentCode
584295
Title
On the Decomposition of Posets
Author
Chen, Yangjun ; Chen, Yibin
Author_Institution
Dept. Appl. Comput. Sci., Univ. of Winnipeg, Winnipeg, MB, Canada
fYear
2012
fDate
11-13 Aug. 2012
Firstpage
134
Lastpage
138
Abstract
In this paper, we propose an efficient algorithm to decompose a partially ordered set S into a minimum set of chains. It requires only O (k×n2) time and space, where n is the num¬ber of the elements in S and k is the size of a maximum anti¬chain of S.
Keywords
computational complexity; set theory; maximum antichain; partially ordered set decomposition; poset decomposition; Algorithm design and analysis; Approximation algorithms; Bipartite graph; Computer science; Data structures; Educational institutions; Joining processes; partially ordered sets; poset decomposition; virtual nodes;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Science & Service System (CSSS), 2012 International Conference on
Conference_Location
Nanjing
Print_ISBN
978-1-4673-0721-5
Type
conf
DOI
10.1109/CSSS.2012.41
Filename
6394279
Link To Document