The Two-Processor Scheduling Problem is in Random NC

DOI10.1137/0218076zbMath0692.68043OpenAlexW1981314573MaRDI QIDQ3034827

Umesh V. Vazirani, Vijay V. Vazirani

Publication date: 1989

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

Full work available at URL: https://hdl.handle.net/1813/6800

zbMATH Keywords

matchingparallel algorithmrandomized algorithmsbasis of a matrixtwo-processor scheduling problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Discrete mathematics in relation to computer science (68R99)

Related Items

Matching is as easy as matrix inversion, 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, An efficient deterministic parallel algorithm for two processors precedence constraint scheduling