Shortest common superstrings and scheduling with coordinated starting times

DOI10.1016/S0304-3975(97)00133-3MaRDI QIDQ1127327zbMATH OpenFDO

Authors Martin Middendorf

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00133-3

zbMATH Keywords

flow-shopjob-shopNP-completenessshortest common superstring problemsuperstrings

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• More on the complexity of common superstring and supersequence problems
• Restricted common superstring and restricted common supersequence
• Shortest consistent superstrings computable in polynomial time
• Algorithms for Three Versions of the Shortest Common Superstring Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 830382 (Why is no real title available?)
• More on the complexity of common superstring and supersequence problems
• On finding minimal length superstrings
• Optimal two- and three-stage production schedules with set-up time included
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem

Cited in

(3)

• Four decades of research on the open-shop scheduling problem to minimize the makespan
• A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
• Recognition of overlap graphs

This page was built for publication: Shortest common superstrings and scheduling with coordinated starting times

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