\(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling

DOI10.1016/0167-6377(95)00031-9zbMath0857.90056WikidataQ59567993 ScholiaQ59567993MaRDI QIDQ1919171

Michael R. Fellows, Hans L. Bodlaender

Publication date: 1 August 1996

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(95)00031-9

zbMATH Keywords

multiprocessor scheduling; partial orders; parameterized complexity; precedence constrained \(K\)-processor scheduling

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

65Y05: Parallel numerical computation

Related Items

Threshold dominating sets and an improved characterization of \(W[2\)]

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Domino Treewidth
• Erratum “Optimal Sequencing of Two Equivalent Processors”
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item