Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0814.06004
Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude
Computing on-line the lattice of maximal antichains of posets. (English)
[J] Order 11, No.3, 197-210 (1994). ISSN 0167-8094; ISSN 1572-9273/e

Summary: We consider the on-line computation of the lattice of maximal antichains of a finite poset $\widetilde{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 $\widetilde{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 ${\cal O}((\vert P\vert + \omega\sp 2(P)) \omega(P)\vert MA(P)\vert)$, where $\vert P\vert$ is the number of elements of the poset $\widetilde{P}$, $\vert MA(P)\vert$ is the number of maximal antichains of $\widetilde{P}$ and $\omega(P)$ is the width of $\widetilde{P}$. This is more efficient than the best off-line algorithms known so far.

MSC 2000:: *06A06 Partial order
68Q25 Analysis of algorithms and problem complexity

Keywords: lattice of maximal antichains of a finite poset; testing distributed computations; on-line algorithm

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]