{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:51Z","timestamp":1759637631025},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208065"},{"type":"electronic","value":"9783642208072"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20807-2_31","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T09:58:49Z","timestamp":1308391129000},"page":"389-403","source":"Crossref","is-referenced-by-count":9,"title":["Jump Number of Two-Directional Orthogonal Ray Graphs"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 A.","family":"Soto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claudio","family":"Telha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","unstructured":"Amilhastre, J., Janssen, P., Vilarem, M.C.: Computing a minimum biclique cover is polynomial for bipartite domino-free graphs. In: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 36\u201342 (1997)"},{"issue":"2-3","key":"31_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0166-218X(02)00570-X","volume":"129","author":"A.A. Bencz\u00far","year":"2003","unstructured":"Bencz\u00far, A.A.: Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems. Discrete Appl. Math.\u00a0129(2-3), 233\u2013262 (2003)","journal-title":"Discrete Appl. Math."},{"key":"31_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-51498-8_7","volume-title":"Fundamentals of Computation Theory","author":"A. Brandst\u00e4dt","year":"1989","unstructured":"Brandst\u00e4dt, A.: The jump number problem for biconvex graphs and rectangle covers of rectangular regions. In: Csirik, J., Demetrovics, J., G\u00e9cseg, F. (eds.) FCT 1989. LNCS, vol.\u00a0380, pp. 68\u201377. Springer, Heidelberg (1989)"},{"key":"31_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: A survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: A survey. SIAM, Philadelphia (1999)"},{"key":"31_CR5","unstructured":"Ceroi, S.: Ordres et g\u00e9om\u00e9trie plane: Application au nombre de sauts. Ph.D. thesis, Universit\u00e9 Montpellier II (2000)"},{"issue":"1","key":"31_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1024417802690","volume":"20","author":"S. Ceroi","year":"2003","unstructured":"Ceroi, S.: A weighted version of the jump number problem on two-dimensional orders is NP-complete. Order\u00a020(1), 1\u201311 (2003)","journal-title":"Order"},{"issue":"4","key":"31_CR7","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/0602042","volume":"2","author":"S. Chaiken","year":"1981","unstructured":"Chaiken, S., Kleitman, D.J., Saks, M., Shearer, J.: Covering regions by rectangles. SIAM J. Algebra Discr.\u00a02(4), 394\u2013410 (1981)","journal-title":"SIAM J. Algebra Discr."},{"key":"31_CR8","first-page":"183","volume":"16","author":"G. Chaty","year":"1979","unstructured":"Chaty, G., Chein, M.: Ordered matchings and matchings without alternating cycles in bipartite graphs. Utilitas Math.\u00a016, 183\u2013187 (1979)","journal-title":"Utilitas Math."},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, B., Skiena, S.: Optimizing combinatorial library construction via split synthesis. In: Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, RECOMB 1999, pp. 124\u2013133 (1999)","DOI":"10.1145\/299432.299467"},{"key":"31_CR10","volume-title":"Introduction to algorithms","author":"T. Cormen","year":"2009","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BFb0019434","volume-title":"Orders, Algorithms and Applications","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E.: The computation of the jump number of convex graphs. In: Bouchitt\u00e9, V., Morvan, M. (eds.) ORDAL 1994. LNCS, vol.\u00a0831, pp. 176\u2013185. Springer, Heidelberg (1994)"},{"issue":"8","key":"31_CR12","first-page":"391","volume":"27","author":"H. Fauck","year":"1991","unstructured":"Fauck, H.: Covering polygons with rectangles via edge coverings of bipartite permutation graphs. J. Inform. Process. Cybernet.\u00a027(8), 391\u2013409 (1991)","journal-title":"J. Inform. Process. Cybernet."},{"key":"31_CR13","volume-title":"Flows in networks","author":"L. Ford","year":"2010","unstructured":"Ford, L., Fulkerson, D.: Flows in networks. Princeton University Press, Princeton (2010)"},{"issue":"3","key":"31_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett.\u00a012(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"31_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jctb.1998.1877","volume":"75","author":"A. Frank","year":"1999","unstructured":"Frank, A.: Finding minimum generators of path systems. J. Comb. Theory, Ser. B\u00a075(2), 237\u2013244 (1999)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1","key":"31_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jctb.1995.1044","volume":"65","author":"A. Frank","year":"1995","unstructured":"Frank, A., Jord\u00e1n, T.: Minimal edge-coverings of pairs of sets. J. Comb. Theory, Ser. B\u00a065(1), 73\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"31_CR17","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.disopt.2008.03.002","volume":"5","author":"A. Frank","year":"2008","unstructured":"Frank, A., V\u00e9gh, L.A.: An algorithm to increase the node-connectivity of a digraph by one. Discrete Optimization\u00a05(4), 677\u2013684 (2008)","journal-title":"Discrete Optimization"},{"issue":"3","key":"31_CR18","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/S0019-9958(84)80012-1","volume":"63","author":"D.S. Franzblau","year":"1984","unstructured":"Franzblau, D.S., Kleitman, D.J.: An algorithm for covering polygons with rectangles. Inform. and Control\u00a063(3), 164\u2013189 (1984)","journal-title":"Inform. and Control"},{"issue":"1","key":"31_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(84)90039-X","volume":"37","author":"E. Gy\u00f6ri","year":"1984","unstructured":"Gy\u00f6ri, E.: A minimax theorem on intervals. J. Comb. Theory, Ser. B\u00a037(1), 1\u20139 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"31_CR20","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"31_CR21","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Irredundant intervals. ACM J. Exp. Algorithmics 1 (1996)","DOI":"10.1145\/235141.235146"},{"key":"31_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, New York (1997)"},{"issue":"2","key":"31_CR23","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0095-8956(91)90073-S","volume":"53","author":"A. Lubiw","year":"1991","unstructured":"Lubiw, A.: A weighted min-max relation for intervals. J. Comb. Theory, Ser. B\u00a053(2), 151\u2013172 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"31_CR24","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00383169","volume":"7","author":"H. M\u00fcller","year":"1990","unstructured":"M\u00fcller, H.: Alternating cycle-free matchings. Order\u00a07, 11\u201321 (1990)","journal-title":"Order"},{"issue":"1-3","key":"31_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0012-365X(94)00350-R","volume":"149","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: On edge perfectness and classes of bipartite graphs. Discrete Mathematics\u00a0149(1-3), 159\u2013187 (1996)","journal-title":"Discrete Mathematics"},{"issue":"3-4","key":"31_CR27","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0025-5564(78)90088-3","volume":"40","author":"D.S. Nau","year":"1978","unstructured":"Nau, D.S., Markowsky, G., Woodbury, M.A., Amos, D.B.: A mathematical analysis of human leukocyte antigen serology. Math. Biosci.\u00a040(3-4), 243\u2013270 (1978)","journal-title":"Math. Biosci."},{"issue":"5","key":"31_CR28","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J. Orlin","year":"1977","unstructured":"Orlin, J.: Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings)\u00a080(5), 406\u2013424 (1977)","journal-title":"Indagationes Mathematicae (Proceedings)"},{"issue":"17","key":"31_CR29","doi-asserted-by":"publisher","first-page":"2383","DOI":"10.1016\/j.dam.2007.07.010","volume":"155","author":"Y. Otachi","year":"2007","unstructured":"Otachi, Y., Okamoto, Y., Yamazaki, K.: Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discrete Applied Mathematics\u00a0155(17), 2383\u20132390 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR30","unstructured":"Pulleyblank, W.R.: Alternating cycle free matchings. Tech. Rep. CORR 82-18, University of Waterloo - Dept. of Combinatorics and Optimization (1982)"},{"key":"31_CR31","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"Shrestha, A.M., Tayu, S., Ueno, S.: On two-directional orthogonal ray graphs. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems, ISCAS 2010, pp. 1807\u20131810 (2010)","DOI":"10.1109\/ISCAS.2010.5537709"},{"key":"31_CR33","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF00340778","volume":"3","author":"G. Steiner","year":"1987","unstructured":"Steiner, G., Stewart, L.K.: A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders. Order\u00a03, 359\u2013367 (1987)","journal-title":"Order"},{"key":"31_CR34","unstructured":"V\u00e9gh, L.A.: Connectivity Augmentation Algorithms. Ph.D. thesis, E\u00f6tv\u00f6s Lor\u00e1nd University (2010)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatoral Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20807-2_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:16:10Z","timestamp":1560284170000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20807-2_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208065","9783642208072"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20807-2_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}