ISSN:
1572-9273
Keywords:
06A10 partial order
;
68C25 computational complexity and efficiency of algorithms
;
68E10 graph theory
;
90C08 special problems of linear programming
;
Bump number
;
jump number
;
polynomial algorithm
;
linear extension
;
bump-critical
;
min-max theorem
;
extension lattice
;
linear circuit layout
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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. 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 order relations) with fixed bump number.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337617
Permalink
