scientific article; zbMATH DE number 3963191

MaRDI QIDQ3731028zbMATH OpenFDO

Authors Ernst W. Mayr, David P. Helmbold

Publication date 1986

zbMATH Keywords

fast parallel computationmatchingparallel algorithm

Mathematics Subject Classification ID

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

Recommendations

• Two Processor Scheduling is in $\mathcal{NC}$
• The Two-Processor Scheduling Problem is in Random NC
• scientific article; zbMATH DE number 176752
• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
• Parallel algorithms for solution of problems in scheduling theory

Cited in

(11)

• Computing the bump number with techniques from two-processor scheduling
• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
• Extending NC and RNC algorithms
• Matching and multidimensional matching in chordal and strongly chordal graphs
• 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
• The Two-Processor Scheduling Problem is in Random NC
• Two Processor Scheduling is in $\mathcal{NC}$
• scientific article; zbMATH DE number 176752 (Why is no real title available?)
• Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality

This page was built for publication:

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