Computing the jump number on semiorders is polynomial
Arnim, Annelie von and Higuera, C. de la
(1994)
Computing the jump number on semiorders is polynomial.
Published in:
Discrete applied mathematics Vol. 51 (12).
pp. 219232.
Abstract
Semiorders from a subclass of interval orders: they can be represented as sets of intervals of a given length. We first prove that semiorders can be partitioned by serialization (or series decomposition) without loss of the jump number aspect. On nonserializable semiorders all linear extensions contain never more than two consecutive bumps (maximal chains of length at most 3). We then give a ''divideandconquer'' argument proving that to solve this case all we need is to be able to compute the number of maximal chains of length at least 2. This can also be dealt with in polynomial time, allowing us to claim that computing the jump number is polynomial on semiorders.
Item Type:  Article 

Citations:  No citation data. 
Uncontrolled Keywords:  interval orders jump number polynomialtime algorithm semiorder 
Subjects: 

Divisions:  Institute of Computer Science 
Related URLs: 
ZAIK Number:  zpr92124 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  18 Oct 2011 15:43 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/124 