An optimal algorithm to find the jump number of partially ordered sets

An optimal algorithm to find the jump number of partially ordered sets

0.00 Avg rating0 Votes
Article ID: iaor19981349
Country: Netherlands
Volume: 8
Issue: 2
Start Page Number: 197
End Page Number: 210
Publication Date: Sep 1997
Journal: Computational Optimization and Applications
Authors: ,
Keywords: posets
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 new heuristic algorithm and an exact algorithm. Performances of both algorithms are experimentally evaluated on a set of randomly generated test problems.

Reviews

Required fields are marked *. Your email address will not be published.