An introduction to multi-parameter complexity analysis of discrete problems

DOI10.1016/j.ejor.2004.04.009zbMath1066.90039OpenAlexW1964857877MaRDI QIDQ1772842

Sergey Sevast'janov

Publication date: 21 April 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.04.009

zbMATH Keywords

Combinatorial optimizationSchedulingColoringComplexity theoryParameterized family of subproblems

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (5)

An alternative approach for proving the NP-hardness of optimization problems ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Parallel machine problems with equal processing times: a survey ⋮ A complete 4-parametric complexity classification of short shop scheduling problems ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan

Cites Work

• The complexity of two group scheduling problems
• Open Shop Scheduling to Minimize Finish Time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An introduction to multi-parameter complexity analysis of discrete problems