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

AlgorithmsMaximum matchingPermutation graphsTwo-processor scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10) 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

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

Cited in

(4)

• Planar stage graphs: Characterizations and applications
• 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)