Article citationsMore>>

C. Grasso and C. Lee, “Combining Partial Order Alignment and Progressive Multiple Sequence Alignment Increases Alignment Speed and Scalability to Very Large Alignment Problems,” Bioinformatics, Vol. 20, No. 10, 2004, pp. 1546-1556. doi:10.1093/bioinformatics/bth126

has been cited by the following article:

• TITLE: The Poset Cover Problem

  AUTHORS: Lenwood S. Heath, Ajit Kumar Nema

  KEYWORDS: Linear Orders; Partial Orders; NP-Completeness; Algorithms

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.3 No.3, July 2, 2013

  ABSTRACT: A partial order or poset P=(X, on a (finite) base set Xdetermines the set L(P)of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P)is #P-complete. A set {P1,P2,...,Pk}of posets on Xcovers the set of linear orders that is the union of the L(Pi). Given linear orders L1,L2,...,Lm on X, the Poset Cover problem is to determine the smallest number of posets that cover {L1,L2,...,Lm}. Here, we show that the decision version of this problem is NP-complete. On the positive side, we explore the use of cover relations for finding posets that cover a set of linear orders and present a polynomial-time algorithm to find a partial poset cover.