Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

DOI10.1007/11841036_6MaRDI QIDQ5449514zbMATH OpenOpenAlexFDO

Authors Monaldo Mastrolilli, Christoph Ambühl

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Single machine precedence constrained scheduling is a Vertex cover problem
• On the approximability of single-machine scheduling with precedence constraints
• Single-Machine Scheduling with Precedence Constraints
• Integer Programming and Combinatorial Optimization
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring

Cited in

(8)

• Single machine precedence constrained scheduling is a Vertex cover problem
• Vertex cover in graphs with locally few colors
• A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data
• On the approximability of single-machine scheduling with precedence constraints
• Vertex cover in graphs with locally few colors
• Near-optimal solutions and large integrality gaps for almost all instances of single-machine precedence-constrained scheduling
• Approximating Precedence-Constrained Single Machine Scheduling by Coloring
• Combination of parallel machine scheduling and vertex cover

This page was built for publication: Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

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