The Two-Processor Scheduling Problem is in Random NC

DOI10.1137/0218076MaRDI QIDQ3034827zbMATH OpenOpenAlexFDO

Authors 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

basis of a matrixmatchingparallel algorithmrandomized algorithmstwo-processor scheduling problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3963191
• Two Processor Scheduling is in $\mathcal{NC}$
• scientific article; zbMATH DE number 176752
• Constructing a perfect matching is in random NC
• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling

Cited in

(9)

• Matching is as easy as matrix inversion
• Extending NC and RNC algorithms
• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
• An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs
• scientific article; zbMATH DE number 3963191 (Why is no real title available?)
• Two Processor Scheduling is in $\mathcal{NC}$
• scientific article; zbMATH DE number 176752 (Why is no real title available?)
• Fast parallel heuristics for the job shop scheduling problem
• An efficient parallel algorithm for scheduling interval ordered tasks

This page was built for publication: The Two-Processor Scheduling Problem is in Random NC

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034827)