Computing the jump number on semi-orders is polynomial

Arnim, Annelie von and Higuera, C. de la (1994) Computing the jump number on semi-orders is polynomial.
Published in: Discrete applied mathematics Vol. 51 (1-2). pp. 219-232.

Abstract

Semi-orders from a subclass of interval orders: they can be represented as sets of intervals of a given length. We first prove that semi-orders can be partitioned by serialization (or series decomposition) without loss of the jump number aspect. On non-serializable semi-orders all linear extensions contain never more than two consecutive bumps (maximal chains of length at most 3). We then give a ''divide-and-conquer'' 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 semi-orders.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr92-124
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 18 Oct 2011 15:43
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/124