Approximating Precedence-Constrained Single Machine Scheduling by Coloring

DOI10.1007/11830924_4MaRDI QIDQ3595374zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli, Ola Svensson, Christoph Ambühl

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• On the approximability of single-machine scheduling with precedence constraints
• scientific article; zbMATH DE number 5605136
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Single machine precedence constrained scheduling is a Vertex cover problem

Cited in

(9)

• Single Machine Scheduling with Precedence Constraints of Dimension 2
• Cross-series-parallel digraphs
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• On the approximability of single-machine scheduling with precedence constraints
• Single machine precedence constrained scheduling is a Vertex cover problem
• Vertex cover in graphs with locally few colors
• An exact algorithm for the precedence-constrained single-machine scheduling problem

This page was built for publication: Approximating Precedence-Constrained Single Machine Scheduling by Coloring

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