Computing the bump number is easy

DOI10.1007/BF00337617MaRDI QIDQ1106863zbMATH OpenOpenAlexFDO

Authors Rolf H. Möhring, George Steiner, M. A. Habib

Publication date 1988

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00337617

zbMATH Keywords

NP-hardpolynomial algorithmlinear extensionbump numbernumber of jumpslinear circuit layout

Mathematics Subject Classification ID

Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3375519 (Why is no real title available?)
• 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
• Minimizing bumps for posets of width two
• Minimizing bumps in linear extensions of ordered sets
• Minimizing bumps in ordered sets by substitution decomposition

Cited in

(14)

• Jump number maximization for proper interval graphs and series-parallel graphs
• Minimizing bumps in linear extensions of ordered sets
• The longest path problem is polynomial on cocomparability graphs
• Computing the bump number with techniques from two-processor scheduling
• The setup polyhedron of series-parallel posets
• 1-tough cocomparability graphs are hamiltonian
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• The longest path problem is polynomial on cocomparability graphs
• Minimizing bumps in ordered sets by substitution decomposition
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Hamiltonian cycle is polynomial on cocomparability graphs
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Minimizing the maximum bump cost in linear extensions of a poset

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)