Two Processor Scheduling is in $\mathcal{NC}$

DOI10.1137/0216050zbMath0634.68023OpenAlexW1556711032MaRDI QIDQ3773326

Ernst W. Mayr, David P. Helmbold

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216050

zbMATH Keywords

parallel algorithmprocessor schedulingcardinality matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

SCHEDULING INTERVAL ORDERS IN PARALLEL ⋮ An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs ⋮ An efficient parallel algorithm for scheduling interval ordered tasks ⋮ Fast parallel heuristics for the job shop scheduling problem ⋮ PARALLEL MAXIMUM MATCHING ALGORITHMS IN INTERVAL GRAPHS ⋮ An efficient deterministic parallel algorithm for two processors precedence constraint scheduling