On two-processor scheduling and maximum matching in permutation graphs

DOI10.1016/0020-0190(96)00018-XMaRDI QIDQ1351633zbMATH OpenOpenAlexFDO

Authors Sarnath Ramnath, Sivaprakasam Sunder

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) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parallel algorithms in computer science (68W10)

Recommendations

• Finding a maximum matching in a permutation graph
• OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS
• scientific article; zbMATH DE number 4049080
• scientific article; zbMATH DE number 176752

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Optimal Sequencing of Two Equivalent Processors
• Optimal scheduling for two-processor systems
• Scheduling Graphs on Two Processors
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(3)

• An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
• scientific article; zbMATH DE number 4147494 (Why is no real title available?)
• scientific article; zbMATH DE number 4074794 (Why is no real title available?)

This page was built for publication: On two-processor scheduling and maximum matching in permutation graphs

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