{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:28Z","timestamp":1725663508751},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540520481"},{"type":"electronic","value":"9783540468721"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-52048-1_31","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:19:53Z","timestamp":1330186793000},"page":"44-55","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal parallel algorithms on circular-arc graphs"],"prefix":"10.1007","author":[{"given":"A. Srinivasa","family":"Rao","sequence":"first","affiliation":[]},{"given":"C. Pandu","family":"Rangan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"4_CR1","unstructured":"M.J.Atallah and D.Z.Chen, Optimal Parallel Algorithm For the Minimum Circle-cover Problem. Tech Rept. CSD-TR-813, Purdue University, Sep 1988."},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(87)90007-X","volume":"26","author":"A. Apostolico","year":"1987","unstructured":"A. Apostolico and S.E. Hambrusch, Finding Maximum Cliques On Circular-arc Graphs, Infom. Proc. Lett., 26 (1987), pp.209\u2013215.","journal-title":"Infom. Proc. Lett."},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"Richard Cole, Parallel Merge Sort, SIAM J. Comp., 17(1988), pp.770\u2013785.","journal-title":"SIAM J. Comp."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, Approximate Parallel Scheduling. Part I: The Basic Technique With Applications To Optimal Parallel List Ranking in Logarithmic Time, SIAM J. Comp., 17 (1988), pp. 128\u2013142.","journal-title":"SIAM J. Comp."},{"key":"4_CR5","volume-title":"Algorithmic Graph Theory And Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Algorithmic Graph Theory And Perfect Graphs (Academic press, New York, 1980)"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"M.C. Golumbic","year":"1988","unstructured":"M.C. Golumbic and Peter L. Hammer, Stability In Circular-Arc Graphs, J. Algorithms, 9 (1988), pp.314\u2013320.","journal-title":"J. Algorithms"},{"key":"4_CR7","volume-title":"Computers and Intractability: A Guide To The Theory of NP-Completeness","author":"M.R. Gary","year":"1979","unstructured":"M.R. Gary and D.S. Johnson, Computers and Intractability: A Guide To The Theory of NP-Completeness (Freeman, San Francisco, CA, 1979)."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/0214018","volume":"14","author":"W.L. Hsu","year":"1985","unstructured":"W.L. Hsu, Maximum Weight Clique Algorithms For Circular-Arc Graphs And Circle Graphs, SIAM J. Comput., 14 (1985), pp.224\u2013231.","journal-title":"SIAM J. Comput."},{"key":"4_CR9","unstructured":"W.L.Hsu and K.H.Tsai, Linear Algorithms On Circular-arc Graphs, unpublished manuscript (1988)."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"P.N. Klein, Efficient Parallel Algorithms For Chordal Graphs. 29th FOCS, 1988, pp.150\u2013161.","DOI":"10.1109\/SFCS.1988.21933"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/0022-0000(88)90006-2","volume":"37","author":"P.N. Klein","year":"1988","unstructured":"P.N. Klein and J.H. Reif, An Efficient Parallel Algorithm For Planarity, J. Comp. Sys. Sci., 37(1988), pp.190\u2013246.","journal-title":"J. Comp. Sys. Sci."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1145\/322217.322232","volume":"24","author":"R.E. Ladner","year":"1980","unstructured":"R.E. Ladner and M.J. Fischer, Parallel Prefix Computation, J. of ACM, 24 (1980), pp.831\u2013838.","journal-title":"J. of ACM"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0217003","volume":"17","author":"S. Masuda","year":"1988","unstructured":"S. Masuda and K. Nakajima, An Optimal Algorithm For Finding a Maximum Independent Set of a Circular-arc Graph, SIAM J. Comput., 17 (1988), pp.41\u201352.","journal-title":"SIAM J. Comput."},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0020-0190(89)90220-2","volume":"31","author":"W.K. Shih","year":"1989","unstructured":"W.K. Shih and W.L. Hsu, An O(n log n+ m log log n) Maximum Weight Clique Algorithm for Circular-Arc Graphs, Inform.Process. Lett.\n31 (1989), pp. 129\u2013134.","journal-title":"Inform.Process. Lett."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"A. Tucker, An Efficient Test For Circular-arc Graphs, SIAM J. Comput., 9(1980), pp.1\u201324.","journal-title":"SIAM J. Comput."},{"key":"4_CR16","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, An Efficient Parallel Biconnectivity Algorithm, SIAM J. Comput., 14(1985), pp. 862\u2013874.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52048-1_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:13:35Z","timestamp":1558253615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52048-1_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540520481","9783540468721"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-52048-1_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}