Computing the bump number is easy

Computing the bump number is easy

0.00 Avg rating0 Votes
Article ID: iaor19881124
Country: Netherlands
Volume: 5
Start Page Number: 107
End Page Number: 129
Publication Date: Nov 1988
Journal: Order
Authors: , ,
Keywords: graphs, programming: linear
Abstract:

The bump number b(P) of a partial order P is the minimum number of comparable adjacent pairs in some linear extension of P. It has an interesting application in the context of linear circuit layout problems. Its determination is equivalent to maximizing the number of jumps in some linear extension of P, for which the corresponding minimization problem (the jump number problem) is known to be NP-hard. The authors derive a polynomial algorithm for determining b(P). The proof of its correctness is based on a min-max theorem involving simple-structured series-parallel partial orders contained in P. This approach also leads to a characterization of all minimal partial orders (with respect to inclusion of the order relations) with fixed bump number.

Reviews

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