On two-processor scheduling and maximum matching in permutation graphs

DOI10.1016/0020-0190(96)00018-XzbMath0900.68227OpenAlexW2091019495MaRDI QIDQ1351633

Sivaprakasam Sunder, Sarnath Ramnath

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00018-x

zbMATH Keywords

AlgorithmsPermutation graphsMaximum matchingTwo-processor scheduling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Optimal scheduling for two-processor systems
• Scheduling Graphs on Two Processors
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Optimal Sequencing of Two Equivalent Processors