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.
- Computing the bump number with techniques from two-processor scheduling
- Minimizing bumps in linear extensions of ordered sets
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- Minimizing bumps in ordered sets by substitution decomposition
- Minimizing bumps for posets of width two
- A combinatorial bijection between linear extensions of equivalent orders
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- An Almost-Linear Algorithm for Two-Processor Scheduling
- Computing the bump number with techniques from two-processor scheduling
- Greedy posets for the bump-minimizing problem
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3375519 (Why is no real title available?)
- Minimizing bumps for posets of width two
- Minimizing bumps in linear extensions of ordered sets
- Minimizing bumps in ordered sets by substitution decomposition
- Minimizing bumps in linear extensions of ordered sets
- Computing the bump number with techniques from two-processor scheduling
- Minimizing bumps in ordered sets by substitution decomposition
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Hamiltonian cycle is polynomial on cocomparability graphs
- 1-tough cocomparability graphs are hamiltonian
- The setup polyhedron of series-parallel posets
- Jump number maximization for proper interval graphs and series-parallel graphs
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- The longest path problem is polynomial on cocomparability graphs
- The longest path problem is polynomial on cocomparability graphs
- Minimizing the maximum bump cost in linear extensions of a poset
- Hamiltonian path in permutation graphs
- The connection between the bump number problem and flow-shop scheduling with precedence constraints
- Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
This page was built for publication: Computing the bump number is easy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106863)
