On the parametric complexity of schedules to minimize tardy tasks.
From MaRDI portal
Publication:1874274
DOI10.1016/S0304-3975(02)00811-3zbMath1038.68049WikidataQ57360052 ScholiaQ57360052MaRDI QIDQ1874274
Michael R. Fellows, Catherine McCartin
Publication date: 25 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, New algorithms for minimizing the weighted number of tardy jobs on a single machine, A general scheme for solving a large set of scheduling problems with rejection in FPT time, On the fine-grained parameterized complexity of partial scheduling to minimize the makespan, A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack, Equitable scheduling on a single machine, Scheduling and fixed-parameter tractability, A multivariate complexity analysis of the material consumption scheduling problem, Polynomial-time data reduction for weighted problems beyond additive goal functions, Unnamed Item, Unnamed Item, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Parameterized complexity of machine scheduling: 15 open problems, Single-machine scheduling with release times, deadlines, setup times, and rejection, Parameterized complexity of a coupled-task scheduling problem, On the parameterized tractability of the just-in-time flow-shop scheduling problem, Scheduling meets \(n\)-fold integer programming, Parameterized complexity of finding subgraphs with hereditary properties.
Cites Work
- Unnamed Item
- Unnamed Item
- Advice classes of parametrized tractability
- Linear extensions of random orders
- On the parameterized complexity of short computation and factorization
- A decomposition theorem for partially ordered sets
- Fixed-Parameter Tractability and Completeness I: Basic Results
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
