{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T16:30:01Z","timestamp":1648744201153},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,3,1]],"date-time":"1993-03-01T00:00:00Z","timestamp":730944000000},"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":[[1993,3]]},"DOI":"10.1007\/bf01190897","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T11:57:59Z","timestamp":1108727879000},"page":"217-238","source":"Crossref","is-referenced-by-count":12,"title":["Efficient parallel recognition of some circular arc graphs, I"],"prefix":"10.1007","volume":"9","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","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.Information Processing Letters,26:209?215, 1987.","journal-title":"Information Processing Letters"},{"issue":"4","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(4):159?165, 1989.","journal-title":"Information Processing Letters"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1073\/pnas.45.11.1607","volume":"45","author":"S. Benzer","year":"1959","unstructured":"S. Benzer. On the topology of the genetic fine structure.Proceedings of the National Academy of Sciences,45:1607?1620, 1959.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"A. A. Bertossi","year":"1983","unstructured":"A. A. Bertossi. Finding Hamiltonian circuits in proper interval graphs.Information Processing Letters,17:97?101, 1983.","journal-title":"Information Processing Letters"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0166-218X(87)90068-0","volume":"16","author":"A. A. Bertossi","year":"1987","unstructured":"A. A. Bertossi and M. A. Bonuccelli. Some parallel algorithms on interval graphs.Discrete Applied Mathematics,16:101?111, 1987.","journal-title":"Discrete Applied Mathematics"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(85)90025-3","volume":"12","author":"M. A. Bonuccelli","year":"1985","unstructured":"M. A. Bonuccelli. Dominating sets and domatic numbers of circular-arc graphs.Discrete Applied Mathematics,12:203?213, 1985.","journal-title":"Discrete Applied Mathematics"},{"key":"CR7","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. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.Journal of Computer and System Sciences,13:335?379, 1976.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(89)90031-8","volume":"32","author":"L. Boxer","year":"1989","unstructured":"L. Boxer and R. Miller. A parallel circle-cover minimization algorithm.Information Processing Letters,32(2):57?60, 1989.","journal-title":"Information Processing Letters"},{"key":"CR9","first-page":"973","volume-title":"Efficient parallel algorithm for several intersection graphs","author":"L. Chen","year":"1989","unstructured":"L. Chen. Efficient parallel algorithm for several intersection graphs. InProceedings of the 22nd International Symposium on Circuits and Systems, Portland, Oregon, May 9?11, pp. 973?976. IEEE, New York, 1989."},{"key":"CR10","first-page":"291","volume-title":"Lecture Notes in Computer Science, Vol. 382","author":"L. Chen","year":"1989","unstructured":"L. Chen. NC algorithms for circular-arc graphs. In F. Dehne, J.-R. Sack, and N. Santoro, editors,Proceedings of the Workshop on Algorithms and Data Structures, Ottawa, Ontario, August 17?19, pp. 291?302. Lecture Notes in Computer Science, Vol. 382. Springer-Verlag, Berlin, 1989."},{"key":"CR11","unstructured":"L. Chen. Efficient parallel algorithms on circular arcs. In J. Urrutia, editor,Proceedings of the 2nd Canadian Conference in Computational Geometry, Ottawa, Ontario, August 6?10, 1990."},{"issue":"3","key":"CR12","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0196-6774(91)90010-V","volume":"12","author":"L. Chen","year":"1991","unstructured":"L. Chen and Y. Yesha. Parallel recognition of the consecutive ones property with applications.Journal of Algorithms,12(3): 375?392, 1991.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"CR13","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort.SIAM Journal on Computing,17(4):770?785, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"CR14","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","volume":"81","author":"R. Cole","year":"1989","unstructured":"R. Cole and U. Vishkin. Faster optimal parallel prefix sums and list ranking.Information and Computation,81(3):334?352, 1989.","journal-title":"Information and Computation"},{"key":"CR15","first-page":"179","volume-title":"Relations between concurrent-write models of parallel computation","author":"F. E. Fich","year":"1984","unstructured":"F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. InProceedings of the 3rd ACM Symposium on Principles of Distributed Computing, Vancouver, B.C., pp. 179?189. Association for Computing Machinery, New York, 1984."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs.Pacific Journal of Mathematics,15:835?855, 1965.","journal-title":"Pacific Journal of Mathematics"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M. R. Garey","year":"1980","unstructured":"M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. The complexity of coloring circular arcs and chords.SIAM Journal on Algebraic and Discrete Methods,1:216?227, 1980.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"F. Gavril","year":"1974","unstructured":"F. Gavril. Algorithms on circular-arc graphs.Networks,4:357?369, 1974.","journal-title":"Networks"},{"key":"CR19","volume-title":"Computer Science and Applied Mathematics","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic.Algorithmic Graph Theory and Perfect Graphs. Computer Science and Applied Mathematics. Academic Press, New York, 1980."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"M. C. Golumbic","year":"1988","unstructured":"M. C. Golumbic and P. L. Hammer. Stability in circular-arc graphs.Journal of Algorithms,9:314?318, 1988.","journal-title":"Journal of Algorithms"},{"key":"CR21","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:459?467, 1982.","journal-title":"Networks"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0890-5401(87)90061-7","volume":"75","author":"X. He","year":"1987","unstructured":"X. He and Y. Yesha. Parallel recognition and decomposition of two terminal series parallel graphs.Information and Computation,75:15?38, 1987.","journal-title":"Information and Computation"},{"key":"CR23","doi-asserted-by":"crossref","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 Journal on Computing,14:224?231, 1985.","journal-title":"SIAM Journal on Computing"},{"key":"CR24","first-page":"842","volume-title":"Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing","author":"W.-L. Hsu","year":"1988","unstructured":"W.-L. Hsu and K. Tsai. Linear time algorithms on circular-arc graphs. InProceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, pp. 842?851. University of Illinois at Urbana-Champaign, 1988."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.2044-8317.1974.tb00534.x","volume":"27","author":"L. Hubert","year":"1974","unstructured":"L. Hubert. Some applications of graph theory and related non-metric techniques to problems of approximate seriation: the case of symmetric proximity measures.British Journal of Mathematical and Statistical Psychology,27:133?153, 1974.","journal-title":"British Journal of Mathematical and Statistical Psychology"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson. The NP-completeness column: an ongoing guide.Journal of Algorithms,6:434?451, 1985.","journal-title":"Journal of Algorithms"},{"key":"CR27","unstructured":"S. K. Kim. Optimal Parallel Algorithms on Sorted Circular Arcs. University of Washington, 1989."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"34","author":"C. P. Kruskal","year":"1985","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix.IEEE Transactions on Computers,34:965?968, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fischer. Parallel prefix computation.Journal of the ACM,27:831?838, 1980.","journal-title":"Journal of the ACM"},{"issue":"2","key":"CR30","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(2):109?115, 1984.","journal-title":"Information Processing Letters"},{"issue":"6","key":"CR31","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1137\/0219071","volume":"19","author":"D. T. Lee","year":"1990","unstructured":"D. T. Lee, M. Sarrafzadeh, and Y. F. Wu. Minimum cuts for circular-arc graphs.SIAM Journal of Computing,19(6):1041?1050, 1990.","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"CR32","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G. S. Lueker","year":"1979","unstructured":"G. S. Lueker and K. S. Booth. A linear time algorithm for deciding interval graph isomorphism.Journal of the ACM,26(2):183?195, 1979.","journal-title":"Journal of the ACM"},{"issue":"1","key":"CR33","doi-asserted-by":"crossref","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 independence set of a circular-arc graph.SIAM Journal on Computing,17(1):41?52, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"CR34","first-page":"274","volume-title":"Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing","author":"A. Moitra","year":"1988","unstructured":"A. Moitra and R. Johnson. PT-optimal algorithms for interval graphs. InProceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, pp. 274?282. University of Illinois at Urbana-Champaign, 1988."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1137\/0602012","volume":"2","author":"J. B. Orlin","year":"1981","unstructured":"J. B. Orlin, M. A. Bonuccelli, and D. P. Bovet. AnO(n 2) algorithm for coloring proper circular arc graphs.SIAM Journal of Algebraic Discrete Methods,2:88?93, 1981.","journal-title":"SIAM Journal of Algebraic Discrete Methods"},{"key":"CR36","unstructured":"F. S. Roberts. Representations of Indifference Relations. Ph.D. thesis, Stanford University, 1968."},{"key":"CR37","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F. S. Roberts","year":"1969","unstructured":"F. S. Roberts. Indifference graphs. In: F. Harary, editor,Proof Techniques in Graph Theory, pp. 139?146. Academic Press, New York, 1969."},{"issue":"1","key":"CR38","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0020-0190(89)90060-4","volume":"32","author":"D. Sarkar","year":"1989","unstructured":"D. Sarkar and I. Stojmenovic. An optimal parallel circle-cover algorithm.Information Processing Letters,32(1): 3?6, 1989.","journal-title":"Information Processing Letters"},{"issue":"3","key":"CR39","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0020-0190(89)90220-2","volume":"3","author":"W.-K. Shih","year":"1989","unstructured":"W.-K. Shih and W.-L. Hsu. AnO(n logn+m log logn) maximum weight clique algorithm for circular arc graphs.Information Processing Letters,3(3):129?134, 1989.","journal-title":"Information Processing Letters"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging, and sorting in a parallel computation model.Journal of Algorithms,2:88?102, 1981.","journal-title":"Journal of Algorithms"},{"issue":"Suppl. 1","key":"CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jcp.1040700403","volume":"70","author":"F. W. Stahl","year":"1967","unstructured":"F. W. Stahl. Circular genetic maps.Journal of Cell Physiology,70(Suppl. 1):1?12, 1967.","journal-title":"Journal of Cell Physiology"},{"key":"CR42","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0041-1647(68)90016-6","volume":"2","author":"K. E. Stouffers","year":"1968","unstructured":"K. E. Stouffers. Scheduling of traffic lights?a new approach.Transportation Research,2:199?234, 1968.","journal-title":"Transportation Research"},{"key":"CR43","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0012-365X(76)80011-8","volume":"16","author":"W. Trotter","year":"1976","unstructured":"W. Trotter and J. Moore. Characterization problems for graphs, partially ordered sets, lattices, and families of sets.Discrete Mathematics,16:361?381, 1976.","journal-title":"Discrete Mathematics"},{"key":"CR44","doi-asserted-by":"crossref","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"A. C. Tucker","year":"1971","unstructured":"A. C. Tucker. Matrix characterization of circular-arc graphs.Pacific Journal of Mathematics,39:535?545, 1971.","journal-title":"Pacific Journal of Mathematics"},{"key":"CR45","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0012-365X(74)80027-0","volume":"7","author":"A. C. Tucker","year":"1974","unstructured":"A. C. Tucker. Structure theorems for some circular-arc graphs.Discrete Mathematics,7:167?195, 1974.","journal-title":"Discrete Mathematics"},{"key":"CR46","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1137\/0129040","volume":"29","author":"A. C. Tucker","year":"1975","unstructured":"A. C. Tucker. Coloring a family of circular-arc graphs.SIAM Journal on Applied Mathematics,29:493?502, 1975.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"CR47","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. C. Tucker","year":"1980","unstructured":"A. C. Tucker. An efficient test for circular-arc graphs.SIAM Journal on Computing,9:1?24, 1980.","journal-title":"SIAM Journal on Computing"},{"key":"CR48","first-page":"126","volume-title":"Proceedings of the IEEE International Conference on Parallel Processing, vol. 3","author":"M. S. Yu","year":"1989","unstructured":"M. S. Yu, C. L. Chen, and R. C. T. Lee. Optimal parallel circle-cover and independent set algorithms for circular-arc graphs. In F. Ris and P. M. Kogge, editors,Proceedings of the IEEE International Conference on Parallel Processing, vol. 3, pp. 126?129. IEEE, New York, 1989."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190897.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190897\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T13:08:25Z","timestamp":1556629705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["BF01190897"],"URL":"https:\/\/doi.org\/10.1007\/bf01190897","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}