The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(83)90045-7zbMath0509.68035OpenAlexW4251271324MaRDI QIDQ4747511

David S. Johnson

Publication date: 1983

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(83)90045-7

zbMATH Keywords

scheduling parallel processorsdirectory assistancetrading hardware for time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem books (00A07) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

An introduction to parallelism in combinatorial optimization ⋮ Minimizing mean flow time with parallel processors and resource constraints ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ Dynamic Relaxations for Online Bipartite Matching ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Interval vertex-coloring of a graph with forbidden colors ⋮ New directions in scheduling theory ⋮ A polynomial feasibility test for preemptive periodic scheduling of unrelated processors