{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:36Z","timestamp":1725663756655},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_229","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:04:57Z","timestamp":1330257897000},"page":"1-13","source":"Crossref","is-referenced-by-count":0,"title":["Computing the all-pairs longest chains in the plane"],"prefix":"10.1007","author":[{"given":"Mikhail J.","family":"Atallah","sequence":"first","affiliation":[]},{"given":"Danny Z.","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. Park. \u201cNotes on Searching in Multidimensional Monotone Arrays (Preliminary Version),\u201d Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp, 497\u2013512.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(92)90200-T","volume":"36","author":"A. Apostolico","year":"1992","unstructured":"A. Apostolico, M. J. Atallah, and S. E. Hambrusch. \u201cNew Clique and Independent Set Algorithms for Circle Graphs,\u201d Discrete Appl. Math., Vol. 36, 1992, pp. 1\u201324.","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"1_CR3","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A. Apostolico","year":"1990","unstructured":"A. Apostolico, M. J. Atallah, L. L. Larmore, and H. S. McFaddin. \u201cEfficient Parallel Algorithms for String Editing and Related Problems,\u201d SIAM J. Comput. 19 (5), 1990, pp. 968\u2013988.","journal-title":"SIAM J. Comput."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1142\/S0218195991000074","volume":"1","author":"M. J. Atallah","year":"1991","unstructured":"M. J. Atallah and D. Z. Chen. \u201cParallel Rectilinear Shortest Paths with Rectangular Obstacles,\u201d Computational Geometry: Theory and Applications, 1, 1991, pp. 79\u2013113.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"M. J. Atallah and S. R. Kosaraju. \u201cAn Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix,\u201d Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, San Francisco, California, 1991, pp. 394\u2013403. (Accepted for publication in J. of Algorithms.)","DOI":"10.1016\/0196-6774(92)90046-F"},{"key":"1_CR6","unstructured":"O. Berkman and U. Vishkin. \u201cFinding Level-Ancestors in Trees,\u201d Tech. Rept. UMIACS-TR-91-9, University of Maryland, 1991."},{"key":"1_CR7","unstructured":"O. Berkman and U. Vishkin. Personal communication."},{"issue":"No.2","key":"1_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent. \u201cThe Parallel Evaluation of General Arithmetic Expressions,\u201d J. of the ACM, Vol. 21, No. 2, 1974, pp. 201\u2013206.","journal-title":"J. of the ACM"},{"key":"1_CR9","unstructured":"B. M. Chazelle. \u201cOptimal Algorithms for Computing Depths and Layers,\u201d Proc. of the 20th Allerton Conference on Communications. Control and Computing, 1983, pp. 427\u2013436."},{"issue":"No.1","key":"1_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00625277","volume":"18","author":"R.B.K. Dewar","year":"1982","unstructured":"R.B.K. Dewar, S.M. Merritt, and M. Sharir. \u201cSome Modified Algorithms for Dijkstra's Longest Upsequence Problem,\u201d Acta Informatica, Vol. 18, No. 1, 1982, pp. 1\u201315.","journal-title":"Acta Informatica"},{"issue":"No.1","key":"1_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288531","volume":"13","author":"E.W. Dijkstra","year":"1980","unstructured":"E.W. Dijkstra. \u201cSome Beautiful Arguments Using Mathematical Induction,\u201d Acta Informatica, Vol. 13, No. 1, 1980, pp. 1\u20138.","journal-title":"Acta Informatica"},{"issue":"No.3","key":"1_CR12","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"S. Even, A. Pnueli, and A. Lempel. \u201cPermutation Graphs and Transitive Graphs,\u201d Journal of the ACM, Vol. 19, No. 3, 1972, pp. 400\u2013410.","journal-title":"Journal of the ACM"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"M.L. Fredman. \u201cOn Computing the Length of Longest Increasing Subsequences,\u201d Discrete Mathematics, 1975, pp. 29\u201335.","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"F. Gavril. \u201cAlgorithms for a Maximum Clique and a Maximum Independent Set of a Circle Graph,\u201d Networks, 1973, pp. 261\u2013273.","DOI":"10.1002\/net.3230030305"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"F. Gavril. \u201cAlgorithms on Circular-Arc Graphs,\u201d Networks, 1974, pp. 357\u2013369.","DOI":"10.1002\/net.3230040407"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"U.I. Gupta, D.T. Lee, and Y.-T. Leung. \u201cEfficient Algorithms for Interval Graphs and Circular Arc Graphs,\u201d Networks, 1982, pp. 459\u2013467.","DOI":"10.1002\/net.3230120410"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"W.-L. Hsu. \u201cMaximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs,\u201d SIAM J. on Computing, 1985, pp. 224\u2013231.","DOI":"10.1137\/0214018"},{"issue":"1","key":"1_CR18","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, A. Lempel, and S. Even. \u201cTransitive Orientation of Graphs and Identification of Permutation Graphs,\u201d Canadian Journal of Math. 23, 1, 1971, pp. 160\u2013175.","journal-title":"Canadian Journal of Math."},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"D. Rotem and U. Urrutia. \u201cFinding Maximum Cliques in Circle Graphs,\u201d Networks, 1981, 1pp. 269\u2013278.","DOI":"10.1002\/net.3230110305"},{"issue":"4","key":"1_CR20","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. \u201cAn Efficient Parallel Biconnectivity Algorithm,\u201d SIAM J. Comput. 14 (4), 1985, pp. 862\u2013874.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_229.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:08:11Z","timestamp":1605647291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_229","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}