Computing the bump number with techniques from two-processor scheduling

DOI10.1007/BF00337618zbMATH Open0652.06003MaRDI QIDQ1106865FDOQ1106865

Authors: Alejandro A. Schäffer, Barbara B. Simons 

Publication date: 1988

Published in: Order (Search for Journal in Brave)

Recommendations

• Computing the bump number is easy
• Minimizing bumps in linear extensions of ordered sets
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• scientific article; zbMATH DE number 221764
• Minimizing bumps for posets of width two

zbMATH Keywords

linear extensionlinear-time algorithmbump numberscheduling unit-time tasks with a precedence partial order on two identical processorstwo-processor scheduling

Mathematics Subject Classification ID

Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• A linear-time algorithm for a special case of disjoint set union
• Optimal scheduling for two-processor systems
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Optimal Sequencing of Two Equivalent Processors
• On Some Variants of the Bandwidth Minimization Problem
• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• Deterministic Scheduling with Pipelined Processors
• Title not available (Why is that?)

Cited In (11)

• Minimizing bumps in linear extensions of ordered sets
• Computing the bump number is easy
• The setup polyhedron of series-parallel posets
• Title not available (Why is that?)
• 1-tough cocomparability graphs are hamiltonian
• The connection between the bump number problem and flow-shop scheduling with precedence constraints
• A comparison of algorithms for minimizing bumps in linear extensions of partial orders
• Hamiltonian cycle is polynomial on cocomparability graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Minimizing the maximum bump cost in linear extensions of a poset

This page was built for publication: Computing the bump number with techniques from two-processor scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106865)