{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T04:05:49Z","timestamp":1751947549040,"version":"3.41.2"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,3,1]],"date-time":"2003-03-01T00:00:00Z","timestamp":1046476800000},"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":["Order"],"published-print":{"date-parts":[[2003,3]]},"DOI":"10.1023\/a:1024417802690","type":"journal-article","created":{"date-parts":[[2003,9,15]],"date-time":"2003-09-15T17:22:37Z","timestamp":1063646557000},"page":"1-11","source":"Crossref","is-referenced-by-count":1,"title":["A Weighted Version of the Jump Number Problem on Two-Dimensional Orders is NP-Complete"],"prefix":"10.1007","volume":"20","author":[{"given":"St\u00e9phan","family":"Ceroi","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"5109557_CR1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0166-218X(94)90111-2","volume":"51","author":"A. Arnim","year":"1994","unstructured":"Arnim, A. and de la Higuera, C.: Computing the jump number on semi-orders is polynomial, Discrete Appl. Math.\n51 (1994), 219\u2013232.","journal-title":"Discrete Appl. Math."},{"key":"5109557_CR2","unstructured":"Asano, T.: Difficulty of the maximum independent set problem on intersection graphs of geometric objects, In: Y. Alavi et al. (eds), Graph Theory, Combinatorics and Application, 1991, pp. 9\u201318."},{"key":"5109557_CR3","series-title":"NATO ASI, Ser. C","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/978-94-009-2639-4_6","volume-title":"Algorithms and Order","author":"V. Bouchitt\u00e9","year":"1989","unstructured":"Bouchitt\u00e9, V. and Habib, M.: The calculation of invariants for ordered sets, In: I. Rival (ed.), Algorithms and Order, NATO ASI, Ser. C 255, Kluwer Acad. Publ., Dordrecht, 1989, pp. 231\u2013279."},{"key":"5109557_CR4","unstructured":"Ceroi, S.: Jump number of 2-dimensional orders and intersection graphs of rectangles, To appear in DMTCS, special issue on ORDAL'99, 2000."},{"key":"5109557_CR5","first-page":"183","volume":"16","author":"G. Chaty","year":"1979","unstructured":"Chaty, G. and Chein, M.: Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Math.\n16 (1979), 183\u2013187.","journal-title":"Utilitas Math."},{"key":"5109557_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1051\/ita\/1979130100031","volume":"13","author":"O. Cogis","year":"1979","unstructured":"Cogis, O. and Habib, M.: Nombre de sauts et graphes s\u00e9rie-parall\u00e8les, RAIRO Inform. Theo.\n13 (1979), 3\u201318.","journal-title":"RAIRO Inform. Theo."},{"key":"5109557_CR7","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00383598","volume":"1","author":"C. Colbourn","year":"1985","unstructured":"Colbourn, C. and Pulleyblank, W.: Minimizing setups in ordered sets of fixed width, Order\n1 (1985), 225\u2013228.","journal-title":"Order"},{"key":"5109557_CR8","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1090\/S0002-9939-1982-0660592-3","volume":"85","author":"D. Duffus","year":"1982","unstructured":"Duffus, D., Rival, I. and Winkler, P.: Minimizing setups for cycle-free ordered sets, Proc. Amer. Math. Soc.\n85 (1982), 509\u2013513.","journal-title":"Proc. Amer. Math. Soc."},{"key":"5109557_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0166-218X(85)80005-6","volume":"11","author":"M. El-Zahar","year":"1985","unstructured":"El-Zahar, M. and Rival, I.: Greedy linear extensions to minimize jumps, Discrete Appl. Math.\n11 (1985), 143\u2013156.","journal-title":"Discrete Appl. Math."},{"key":"5109557_CR10","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1137\/0214068","volume":"14","author":"U. Faigle","year":"1985","unstructured":"Faigle, U., Gierz, G. and Schrader, R.: Algorithmic approach to setup minimization, SIAM J. Comput.\n14 (1985), 954\u2013965.","journal-title":"SIAM J. Comput."},{"key":"5109557_CR11","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0167-6377(85)90027-6","volume":"4","author":"U. Faigle","year":"1985","unstructured":"Faigle, U. and Schrader, R.: A setup heuristic for interval orders, Oper. Res. Lett.\n4 (1985), 185\u2013188.","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"5109557_CR12","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00346129","volume":"6","author":"S. Felsner","year":"1990","unstructured":"Felsner, S.: A 3\/2-approximation algorithm for the jump number of interval orders, Order\n6(4) (1990), 325\u2013334.","journal-title":"Order"},{"key":"5109557_CR13","unstructured":"Felsner, S.: Interval orders: combinatorial structure and algorithms, Technische Universit\u00e4t Berlin, Fachbereich Mathematik, 1992."},{"key":"5109557_CR14","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/S0019-9958(84)80012-1","volume":"63","author":"D. S. Franzblau","year":"1984","unstructured":"Franzblau, D. S. and Kleitman, D. J.: An algorithm for covering polygons with rectangles, Information and Control\n63 (1984), 164\u2013189.","journal-title":"Information and Control"},{"key":"5109557_CR15","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S. and Stockmeyer, L.: Some simplified NP-complete graph problems, Theoret. Comput. Sci.\n1 (1976), 237\u2013267.","journal-title":"Theoret. Comput. Sci."},{"key":"5109557_CR16","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0166-218X(97)00076-0","volume":"81","author":"Y. Liu","year":"1998","unstructured":"Liu, Y., Morgana, A. and Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Discrete Appl. Math.\n81 (1998), 69\u201391.","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"5109557_CR17","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1137\/0403010","volume":"3","author":"A. Lubiw","year":"1990","unstructured":"Lubiw, A.: The boolean basis problem and how to cover some polygons by rectangles, SIAM J. Discrete Math.\n3(1) (1990), 98\u2013115.","journal-title":"SIAM J. Discrete Math."},{"key":"5109557_CR18","series-title":"NATO ASI, Ser. C","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\u00f6hring","year":"1989","unstructured":"M\u00f6hring, R. H.: Computationally tractable classes of ordered sets, In: I. Rival (ed.), Algorithms and Order, NATO ASI, Ser. C 255, Kluwer Acad. Publ., Dordrecht, 1989, pp. 105\u2013193."},{"key":"5109557_CR19","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00383398","volume":"8","author":"J. Mitas","year":"1991","unstructured":"Mitas, J.: Tackling the jump number of interval orders, Order\n8 (1991), 115\u2013132.","journal-title":"Order"},{"key":"5109557_CR20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF00383169","volume":"7","author":"H. M\u00fcller","year":"1990","unstructured":"M\u00fcller, H.: Alternating cycle-free matchings, Order\n7 (1990), 11\u201321.","journal-title":"Order"},{"key":"5109557_CR21","unstructured":"Pulleyblank, W.: Alternating cycle-free matchings, Technical Report 82-18, Dept. of Combinatorics and Optimization, University of Waterloo, 1982."},{"issue":"9","key":"5109557_CR22","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/81.414831","volume":"42","author":"C. S. Rim","year":"1995","unstructured":"Rim, C. S. and Nakajima, K.: On rectangle intersection and overlap graphs, IEEE Trans. Circuits Systems I\n42(9) (1995), 549\u2013553.","journal-title":"IEEE Trans. Circuits Systems I"},{"key":"5109557_CR23","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF00383447","volume":"8","author":"A. Sharary","year":"1991","unstructured":"Sharary, A.: The jump number of Z-free ordered sets, Order\n8 (1991), 267\u2013273.","journal-title":"Order"},{"key":"5109557_CR24","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF00340778","volume":"3","author":"G. Steiner","year":"1987","unstructured":"Steiner, G. and Stewart, L. K.: A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders, Order\n3 (1987), 359\u2013367.","journal-title":"Order"},{"key":"5109557_CR25","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0012-365X(94)00290-Y","volume":"1\u20133","author":"M. M. Sys\u0142o","year":"1995","unstructured":"Sys\u0142o, M. M.: The jump number problem on interval orders: A 3\/2 approximation algorithm, Discrete Math.\n1\u20133 (1995), 119\u2013130.","journal-title":"Discrete Math."}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1024417802690.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1024417802690\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1024417802690.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T08:52:09Z","timestamp":1751878329000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1024417802690"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,3]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,3]]}},"alternative-id":["5109557"],"URL":"https:\/\/doi.org\/10.1023\/a:1024417802690","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2003,3]]}}}