Computing the bump number is easy
From MaRDI portal
Publication:1106863
DOI10.1007/BF00337617zbMath0652.06002OpenAlexW2088579252MaRDI QIDQ1106863
George Steiner, Rolf H. Möhring, Michel A. Habib
Publication date: 1988
Published in: Order (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00337617
Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Related Items
Computing the bump number with techniques from two-processor scheduling ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ The setup polyhedron of series-parallel posets ⋮ Minimizing bumps in ordered sets by substitution decomposition ⋮ Minimizing the maximum bump cost in linear extensions of a poset ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Multigraph realizations of degree sequences: Maximization is easy, minimization is hard ⋮ Hamiltonian cycle is polynomial on cocomparability graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ The connection between the bump number problem and flow-shop scheduling with precedence constraints ⋮ Jump number maximization for proper interval graphs and series-parallel graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Minimizing bumps in linear extensions of ordered sets
- A combinatorial bijection between linear extensions of equivalent orders
- Greedy posets for the bump-minimizing problem
- Computing the bump number with techniques from two-processor scheduling
- Minimizing bumps for posets of width two
- Minimizing bumps in ordered sets by substitution decomposition
- A comparison of algorithms for minimizing bumps in linear extensions of partial orders
- An Almost-Linear Algorithm for Two-Processor Scheduling
