The jump number of a partially ordered set (poset) P is the minimum number of incomparable adjacent pairs ( jumps) in some linear extension of P. The problem of finding a linear extension of P with minimum number of jumps ( jump number problem) is known to be NP-hard in general and, at the best of our knowledge, no exact algorithm for general posets has been developed. In this paper, we give examples of applications of this problem and propose for the general case a newheuristic algorithm and an exact algorithm. Performances of both algorithms are experimentally evaluated on a set of randomly generated test problems.
Bianco, L., Dell'Olmo, P., Giordani, S. (1997). An Optimal Algorithm to Find the Jump Number of Partially Ordered Sets. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 8, 197-210 [10.1023/A:1008625405476].
An Optimal Algorithm to Find the Jump Number of Partially Ordered Sets
BIANCO, LUCIO;GIORDANI, STEFANO
1997-01-01
Abstract
The jump number of a partially ordered set (poset) P is the minimum number of incomparable adjacent pairs ( jumps) in some linear extension of P. The problem of finding a linear extension of P with minimum number of jumps ( jump number problem) is known to be NP-hard in general and, at the best of our knowledge, no exact algorithm for general posets has been developed. In this paper, we give examples of applications of this problem and propose for the general case a newheuristic algorithm and an exact algorithm. Performances of both algorithms are experimentally evaluated on a set of randomly generated test problems.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
