Computing on-line the lattice of maximal antichains of posets | Zendy

Guy-Vincent Jourdan | Zendy; Jean-Xavier Rampon | Zendy; Claude Jard | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computing on-line the lattice of maximal antichains of posets

Author(s) -

Guy-Vincent Jourdan,

Jean-Xavier Rampon,

Claude Jard

Publication year - 1994

Publication title -

order

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.465

H-Index - 27

eISSN - 1572-9273

pISSN - 0167-8094

DOI - 10.1007/bf02115811

Subject(s) - partially ordered set , combinatorics , mathematics , lattice (music) , computation , omega , discrete mathematics , vertex (graph theory) , real line , graph , algorithm , physics , quantum mechanics , acoustics

We consider the on-line computation of the lattice of maximal antichains of a finite poset $\tilde P$ . This on-line computation satisfies what we call the “linear extension hypothesis”: the new incoming vertex is always maximal in the current subposet of $\tilde P$ . In addition to its theoretical interest, this abstraction of the lattice of antichains of a poset has structural properties which give it interesting practical behavior. In particular, the lattice of maximal antichains may be useful for testing distributed computations, for which purpose the lattice of antichains is already widely used. Our on-line algorithm has a run time complexity of $\mathcal{O}((\left| P \right| + \omega ^2 (P))\omega (P)\left| {MA(P)} \right|),$ , where |P| is the number of elements of the poset, $\tilde P$ , |MA(P)| is the number of maximal antichains of $\tilde P$ and ω(P) is the width of $\tilde P$ . This is more efficient than the best off-line algorithms known so far.