{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T10:38:39Z","timestamp":1772620719440,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1995,11,1]],"date-time":"1995-11-01T00:00:00Z","timestamp":815184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,11]]},"DOI":"10.1007\/bf01192049","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T16:40:03Z","timestamp":1108658403000},"page":"429-441","source":"Crossref","is-referenced-by-count":21,"title":["An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications"],"prefix":"10.1007","volume":"14","author":[{"given":"M. J.","family":"Atallah","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. Z.","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. T.","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0020-0190(89)90037-9","volume":"32","author":"M. J. Atallah","year":"1989","unstructured":"M. J. Atallah and D. Z. Chen, An optimal parallel algorithm for the minimum circle-cover problem,Information Processing Letters,32, 1989, 159?165.","journal-title":"Information Processing Letters"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(88)90068-3","volume":"27","author":"A. A. Bertossi","year":"1988","unstructured":"A. A. Bertossi, Parallel circle-cover algorithms,Information Processing Letters,27, 1988, 133?139.","journal-title":"Information Processing Letters"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Luekher, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms,Journal of Computer and System Sciences,13, 1976, 335?379.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1109\/IPPS.1994.288297","volume-title":"Proceedings of the 8thtInternational Parallel Processing Symposium","author":"D. Z. Chen","year":"1994","unstructured":"D. Z. Chen and D. T. Lee, solving the all-pair shortest path problem on interval and circular-arc graphs,Proceedings of the 8thtInternational Parallel Processing Symposium, Cancun, Mexico, April 1994, pp. 224?228."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union,Journal of Computer and System Sciences,30, 1985, 209?221.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR7","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":"CR8","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U. I. Gupta","year":"1982","unstructured":"U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, Efficient algorithms for interval graphs and circular-arc graphs,Networks,12, 1982, 459?467.","journal-title":"Networks"},{"key":"CR9","first-page":"575","volume-title":"Proceedings of the 30th Annual Allerton Conference on Communication, Control, and Computing","author":"O. H. Ibarra","year":"1992","unstructured":"O. H. Ibarra, H. Wang, and Q. Zheng, Minimum cover and single source shortest path problems for weighted interval graphs and circular-arc graphs,Proceedings of the 30th Annual Allerton Conference on Communication, Control, and Computing, 1992, University of Illinois, Urbana, pp. 575?584."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(84)90033-4","volume":"18","author":"C. C. Lee","year":"1984","unstructured":"C. C. Lee and D. T. Lee, On a circle-cover minimization problem,Information Processing Letters,18, 1984, 109?115.","journal-title":"Information Processing Letters"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/net.3230220103","volume":"22","author":"R. Ravi","year":"1992","unstructured":"R. Ravi, M. V. Marathe, and C. P. Rangan, An optimal algorithm to solve the all-pair shortest path problem on interval graphs,Networks,22, 1992, 21?35.","journal-title":"Networks"},{"issue":"1","key":"CR12","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1142\/S0218195994000057","volume":"4","author":"M. Sarrafzadeh","year":"1994","unstructured":"M. Sarrafzadeh and D. T. Lee, Restricted track assignment with applications,International Journal of Computational Geometry & Applications,4(1), March 1994, 53?68.","journal-title":"International Journal of Computational Geometry & Applications"},{"issue":"2","key":"CR13","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan, A class of algorithms which require nonlinear time to maintain disjoint sets,Journal of Computer and System Sciences,18(2), 1979, 110?127.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"CR14","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas Van","year":"1977","unstructured":"P. Van Emde Boas, Preserving order in a forest in less than logarithmic time and linear space,Information Processing Letters,6(3), 1977, 80?82.","journal-title":"Information Processing Letters"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192049.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01192049\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T09:08:49Z","timestamp":1556615329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01192049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["BF01192049"],"URL":"https:\/\/doi.org\/10.1007\/bf01192049","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}