Computing the jump number on semi-orders is polynomial (Q1329825)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing the jump number on semi-orders is polynomial |
scientific article |
Statements
Computing the jump number on semi-orders is polynomial (English)
0 references
22 September 1994
0 references
Semi-orders form a subclass of interval orders: they can be represented by intervals of unit length. The paper gives an \(O(n^{3.5})\) algorithm computing the jump number of a semiorder of \(n\) elements.
0 references
polynomial-time algorithm
0 references
interval orders
0 references
jump number
0 references
semiorder
0 references
