Computing the jump number on semi-orders is polynomial (Q1329825)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Computing the jump number on semi-orders is polynomial |
scientific article; zbMATH DE number 612447
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing the jump number on semi-orders is polynomial |
scientific article; zbMATH DE number 612447 |
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
