{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T13:51:23Z","timestamp":1761486683394,"version":"3.41.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1999,12,1]],"date-time":"1999-12-01T00:00:00Z","timestamp":944006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,12,1]],"date-time":"1999-12-01T00:00:00Z","timestamp":944006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1999,12]]},"DOI":"10.1023\/a:1009827520712","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"417-435","source":"Crossref","is-referenced-by-count":7,"title":["Transversal Graphs for Partially Ordered Sets: Sequencing, Merging and Scheduling Problems"],"prefix":"10.1007","volume":"3","author":[{"given":"Martin","family":"Middendorf","sequence":"first","affiliation":[]},{"given":"Vadim G.","family":"Timkovsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"244017_CR1","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/opre.4.2.244","volume":"4","author":"S.B. Ackers","year":"1956","unstructured":"S.B. Ackers, \"A graphical approach to production scheduling problems,\" Oper. Res., vol. 4, pp. 244\u2013245, 1956.","journal-title":"Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"M. Aigner, Combinatorial Theory, Springer-Verlag, 1979.","key":"244017_CR2","DOI":"10.1007\/978-1-4615-6666-3"},{"key":"244017_CR3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01719698","volume":"16","author":"P. Brucker","year":"1994","unstructured":"P. Brucker, \"A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs,\" OR Spectrum, vol. 16, pp. 5\u20137, 1994.","journal-title":"OR Spectrum"},{"key":"244017_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03088-2","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"1995","unstructured":"P. Brucker, Scheduling Algorithms, Springer: Berlin, 1995."},{"key":"244017_CR5","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0377-2217(95)00350-9","volume":"90","author":"P. Brucker","year":"1996","unstructured":"P. Brucker and A. Kr\u00a8amer, \"Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems,\" EJOR, vol. 90, pp. 214\u2013226, 1996.","journal-title":"EJOR"},{"key":"244017_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/PL00020906","volume":"49","author":"P. Brucker","year":"1999","unstructured":"P. Brucker, S.A. Kravchenko, and Y.N. Sotskov, \"Preemptive job-shop scheduling problems with a fixed number of jobs,\" Mathematical Methods of Operations Research, vol. 49, pp. 41\u201376, 1999.","journal-title":"Mathematical Methods of Operations Research"},{"key":"244017_CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0004-3702(92)90016-Q","volume":"57","author":"D.E. Foulser","year":"1992","unstructured":"D.E. Foulser, M. Li, and Q. Yang, \"Theory and algorithms for plan merging,\" Artificial Intelligence, vol. 57, pp.143\u2013181, 1992.","journal-title":"Artificial Intelligence"},{"key":"244017_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0304-3975(95)00138-7","volume":"165","author":"C. Fraser","year":"1996","unstructured":"C. Fraser, \"Consistent subsequences and supersequences,\" Theoret. Comput. Sci., vol. 165, pp. 233\u2013246, 1996.","journal-title":"Theoret. Comput. Sci."},{"key":"244017_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1006\/inco.1996.0011","volume":"124","author":"C.B. Fraser","year":"1996","unstructured":"C.B. Fraser, R.W. Irving, and M. Middendorf, \"Maximal common subsequences and minimal common supersequences,\" Information and Computation, vol. 124, no. 2, pp. 145\u2013153, 1996.","journal-title":"Information and Computation"},{"key":"244017_CR10","volume-title":"Computers and Intractability: AGuide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-Completeness, Freeman: San Francisco, 1979."},{"key":"244017_CR11","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/3-540-56279-6_99","volume":"650","author":"K. Hakata","year":"1992","unstructured":"K. Hakata and H. Imai, \"The longest common subsequence problem for small alphabet size between many strings,\" Lect. Notes in Comput. Sci., vol. 650, pp. 469\u2013478, 1992.","journal-title":"Lect. Notes in Comput. Sci."},{"key":"244017_CR12","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0022-0000(84)90025-4","volume":"29","author":"W.J. Hsu","year":"1984","unstructured":"W.J. Hsu and M.W. Du, \"New algorithm for the LCS problem,\" J. Comput. and System Sci., vol. 29, pp. 133\u2013152, 1984.","journal-title":"J. Comput. and System Sci."},{"key":"244017_CR13","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/3-540-56024-6_18","volume":"644","author":"R.W. Irving","year":"1992","unstructured":"R.W. Irving and C.B. Fraser, \"Two algorithms for the longest common subsequence of 3 (or more) strings,\" Lect. Notes in Comput. Sci., vol. 644, pp. 214\u2013229, 1992.","journal-title":"Lect. Notes in Comput. Sci."},{"key":"244017_CR14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BF01934067","volume":"21","author":"S.Y. Itoga","year":"1981","unstructured":"S.Y. Itoga, \"The string merging problem,\" BIT, vol. 21, pp. 20\u201330, 1981.","journal-title":"BIT"},{"key":"244017_CR15","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(93)90167-R","volume":"119","author":"T. Jiang","year":"1992","unstructured":"T. Jiang and M. Li, \"On the complexity of learning strings and sequences,\" Theoret. Comput. Sci., vol. 119, pp. 363\u2013371, 1992.","journal-title":"Theoret. Comput. Sci."},{"unstructured":"A. Kr\u00a8amer, \"Scheduling multiprocessor tasks on dedicated processors,\" Diss., Fachbereich Mathematik\/ Informatik, Universit\u00a8at Osnabr\u00a8uck, Osnabr\u00a8uck, 1995.","key":"244017_CR16"},{"key":"244017_CR17","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart andWinston: New York, 1976."},{"key":"244017_CR18","series-title":"Logistics of Production and Inventory","first-page":"445","volume-title":"Handbook on Operations Research and Management Science","author":"E.L. Lawler","year":"1993","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, \"Sequencing and scheduling: algorithms and complexity,\" in Handbook on Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory, S.C. Graves, A.H.G. Rinnooy Kan, and P. Zipkin (Eds.), Elsevier Science Publishers, B.V.: Amsterdam, pp. 445\u2013552, 1993."},{"unstructured":"W. Meyer, \"Geometrische Methoden zur L\u00a8osung von Job-shop Problemen und derenVerallgemeinerungen,\" Diss., Faculty of Mathematics and Computer Science, University of Osnabr\u00a8uck, 1992. (German).","key":"244017_CR19"},{"key":"244017_CR20","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(95)00014-N","volume":"145","author":"M. Middendorf","year":"1994","unstructured":"M. Middendorf, \"On finding minimal, maximal and consistent sequences over a binary alphabet,\" Theoret. Comput. Sci., vol. 145, pp. 317\u2013327, 1994.","journal-title":"Theoret. Comput. Sci."},{"key":"244017_CR21","series-title":"Lecture Notes in Operations Research","first-page":"60","volume-title":"Proc. Third International Symposium on Operations Research and Its Applications (ISORA'98)","author":"M. Middendorf","year":"1998","unstructured":"M. Middendorf and V.G. Timkovsky, \"Transversal Graphs in Plan Merging and Related Problems,\" in Proc. Third International Symposium on Operations Research and Its Applications (ISORA'98), Lecture Notes in Operations Research 3, World Publishing. Corp., Beijing, 1998, pp. 60\u201374."},{"key":"244017_CR22","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2639-4_4","volume-title":"Algorithms and Order","author":"R.H. M\u00a8ohring","year":"1989","unstructured":"R.H. M\u00a8ohring, \"Computationally tractable classes of ordered sets,\" in Algorithms and Order, I. Rival (Ed.), Kluwer Academic: Dordrecht, pp. 105\u2013193, 1989."},{"doi-asserted-by":"crossref","unstructured":"A.R. Rubinov and V.G. Timkovsky, \"Nonsimilarity combinatorial problems,\" I, BioSystems, vol. 30, 1993, pp. 81\u201392, II, in Computer Genetics, P.A. Pevzner and M.S. Gelfand (Ed.), Elsevier, 1993, pp. 81\u201392.","key":"244017_CR23","DOI":"10.1016\/0303-2647(93)90064-J"},{"key":"244017_CR24","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1137\/S0895480192234277","volume":"11","author":"A.R. Rubinov","year":"1998","unstructured":"A.R. Rubinov and V.G. Timkovsky, \"String noninclusion optimization problems,\" SIAM J. Discrete Math., vol. 11, pp. 456\u2013467, 1998.","journal-title":"SIAM J. Discrete Math."},{"key":"244017_CR25","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/0377-2217(91)90066-5","volume":"53","author":"Y. Sotskov","year":"1991","unstructured":"Yu.N. Sotskov, \"The complexity of shop scheduling problems with two or three jobs,\" EJOR, vol. 53, pp. 326\u2013336, 1991.","journal-title":"EJOR"},{"key":"244017_CR26","first-page":"1","volume":"25","author":"V.G. Timkovsky","year":"1989","unstructured":"V.G. Timkovsky, \"Complexity of common subsequence and supersequence problems and related problems,\" Kibernetika, no. 5, pp. 1\u201313, 1989 (in Russian); English transl. in Cybernetics, vol. 25, pp. 565\u2013580, 1990.","journal-title":"Kibernetika"},{"key":"244017_CR27","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0304-3975(94)00257-J","volume":"143","author":"L. Zhang","year":"1995","unstructured":"L. Zhang, \"On the approximation of longest common non-supersequences and shortest common nonsubsequences,\" Theoret. Comput. Sci., vol. 143, pp. 353\u2013362, 1995.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009827520712.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009827520712\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009827520712.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:12:54Z","timestamp":1751281974000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009827520712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1999,12]]}},"alternative-id":["244017"],"URL":"https:\/\/doi.org\/10.1023\/a:1009827520712","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[1999,12]]}}}