
doi: 10.1007/bf00337891
Given a partially ordered set \(P=({\mathbb{P}},<_ P)\) the authors define the deficiency D(P) of a partial order as the number of incomparable pairs. Since it is not always straightforward to estimate D(P), they introduce an alternative way to estimate D(P), they introduce an alternative way to estimate D(P) by introducing another measure for P which they call the spread of P-S(P). In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the patial order is only implicitly defined, the spread of the patial order is easier to estimate directly and provides a convenient way to estimate the deficiency. Then they give sharp bounds for the relationship between D(P) and S(P).
partially ordered set, sorting and selection algorithms, Partial orders, general, spread, deficiency, Searching and sorting, number of incomparable pairs
partially ordered set, sorting and selection algorithms, Partial orders, general, spread, deficiency, Searching and sorting, number of incomparable pairs
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
