Technical Report 195-1988
- Title
- Computing The Bump Number of Ordered Sets is Easy
- Authors
- Michel Habib, Rolf H. Möhring, and George Steiner
- Publication
- ORDER, vol. 5, 1988, pp. 107-129
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
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 {it maximizing} the number of jumps in some linear extension of P, for which the corresponding {it minimization problem} (the jump number problem) is known to be NP-hard. We 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 ordered relations) with fixed bump number.