Approximating Precedence-Constrained Single Machine Scheduling by Coloring

DOI10.1007/11830924_4zbMATH Open1155.90373OpenAlexW1496117300MaRDI QIDQ3595374FDOQ3595374

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

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

Mathematics Subject Classification ID

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

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)