{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:13Z","timestamp":1725664453000},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:03:26Z","timestamp":1330290206000},"page":"169-180","source":"Crossref","is-referenced-by-count":0,"title":["Parallel comparability graph recognition and modular decomposition"],"prefix":"10.1007","author":[{"given":"Michel","family":"Morvan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Viennot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Richard Cole. Parallel merge sort. SIAM J. Comput., 17(4), August 1988.","DOI":"10.1137\/0217049"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in algebra and programming\u2014CAAP 94 (Edinburgh) Lecture Notes in Computer Science, volume 787","author":"A. Cournier","year":"1994","unstructured":"A. Cournier and M. Habib. A new linear algorithm of modular decomposition. In Trees in algebra and programming\u2014CAAP 94 (Edinburgh) Lecture Notes in Computer Science, volume 787, pages 68\u201384, Berlin, 1994. Springer."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Elias Dalhaus. Efficient parallel modular decomposition. In WG '95 21st International Workshop on Graph-Theoretic Concepts in Computer Science. M. Nagl, 1995. To appear in Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-60618-1_83"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Tibor Gallai. Transitiv orientierbare graphen. Acta Math. Acad. Scient. Hung. Tom., 18:25\u201366, 1967.","journal-title":"Acta Math. Acad. Scient. Hung. Tom."},{"key":"15_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":"15_CR6","first-page":"536","volume-title":"Linear-time modular decomposition and efficient transitive orientation of comparability graphs","author":"M.R. McConnell","year":"1994","unstructured":"M.R. McConnell and J. Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA), pages 536\u2013545, New York, 1994. ACM."},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-94-009-5315-4_2","volume-title":"Graphs and Orders","author":"R. H. Mohring","year":"1985","unstructured":"Rolf H. Mohring. Algorithmic aspects of comparability graphs and interval graphs. In I. Rival, editor, Graphs and Orders, pages 41\u2013101. D. Reidel Publishing Company, Dordrecht, 1985."},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2639-4_4","volume-title":"Algorithms and Order","author":"R. H. Mohring","year":"1989","unstructured":"Rolf H. Mohring. Computationally tractable classes of ordered sets. In I. Rival, editor, Algorithms and Order, pages 105\u2013193. Kluwer Acad. Publ., Dordrecht, 1989."},{"key":"15_CR9","unstructured":"Mark B. Novick. Fast parallel algorithms for the modular decomposition. Technical Report 89-1016, Cornell University, 1989."},{"key":"15_CR10","unstructured":"Mark B. Novick. Logaithmic time parallel algorithms for recognizing comparability and interval graphs. Technical Report 89-1015, Cornell University, 1989."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloah","year":"1982","unstructured":"Y. Shiloah and U. Vishkin. An O(log n) parallel connectivity algorithm. J. Algorithms, 3:57\u201367, 1982.","journal-title":"J. Algorithms"},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan. An efficient parallel biconnectivity algorithm. SIAM J. Computing, 14:862\u2013874, 1985.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T10:08:46Z","timestamp":1640945326000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}