A polynomial algorithm for recognizing the A-order class

DOI10.1016/J.DISC.2008.10.032MaRDI QIDQ1043599zbMATH OpenOpenAlexFDO

Authors A. Moukrim, Eric Sanlaville

Publication date 9 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.10.032

zbMATH Keywords

polynomial complexityrecognition algorithmpreemptive scheduling\(\mathcal A_m\)-orders

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Optimal scheduling on parallel machines for a new order class
• Scheduling Flat Graphs
• Scheduling precedence graphs of bounded height
• scientific article; zbMATH DE number 962288
• scientific article; zbMATH DE number 512916

Cites work

• scientific article; zbMATH DE number 3908482 (Why is no real title available?)
• A relation between multiprocessor scheduling and linear programming
• Optimal preemptive scheduling on a fixed number of identical parallel machines
• Preemptive scheduling of interval orders is polynomial
• Scheduling Interval-Ordered Tasks
• Scheduling preemptive jobs with precedence constraints on parallel machines
• Scheduling unitary task systems with zero--one communication delays for quasi-interval orders
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders

Cited in

(1)

• scientific article; zbMATH DE number 14735 (Why is no real title available?)

This page was built for publication: A polynomial algorithm for recognizing the \(\mathcal A\)-order class

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