{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:16Z","timestamp":1742598616435,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58715-2_123","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:41:19Z","timestamp":1330274479000},"page":"171-180","source":"Crossref","is-referenced-by-count":7,"title":["Efficient parallel and linear time sequential split decomposition (extended abstract)"],"prefix":"10.1007","author":[{"given":"Elias","family":"Dahlhaus","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"15_CR1","volume-title":"Diplom Thesis","author":"A. Barten","year":"1989","unstructured":"A. Barten, Design of Very Fast Parallel Algorithms in the Combinatorial Optimization (German), Diplom Thesis, RWTH Aaachen, 1989."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A. Bouchet","year":"1987","unstructured":"A. Bouchet, Reducing Prime Graphs and Recognizing Circle Graphs, Combinatorial,7 (1987), pp. 243\u2013254.","journal-title":"Combinatorial"},{"key":"15_CR3","unstructured":"R. Cole, Parallel Merge Sort, 27. IEEE-FOCS (1986), pp. 511\u2013516."},{"key":"15_CR4","unstructured":"A. Cournier, M. Habib, A New Linear Time Algorithm for Modular Decomposition, Trees in Algebra and Prograrnming-CAAP'94, (S. Tison ed.) LNCS 787, (1994), pp. 68\u201384."},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"W. Cunningham","year":"1982","unstructured":"W. Cunningham, Decomposition of Directed Graphs, SIAM Journal on Algebraic and Discrete Methods, 3 (1982), pp. 214\u2013228.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"15_CR6","unstructured":"E. Dahlhaus, Efficient Parallel Algorithms to Recognize Cographs and Distance Hereditary Graphs, to appear in Discrete Applied Mathematics."},{"key":"15_CR7","unstructured":"E. Dahlhaus, Efficient Parallel Modular Decomposition, submitted."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, An Efficient Parallel Recognition Algorithm of Parity Graphs, ICCI 93, 0. Abou-Rabia et al. ed., pp. 82\u201386.","DOI":"10.1109\/ICCI.1993.315399"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, Fast Parallel Algorithm for the Single Link Heuristics of Hierarchical Clustering, Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing (1992), pp. 184\u2013186.","DOI":"10.1109\/SPDP.1992.242746"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1006\/jagm.1994.1013","volume":"16","author":"A. Ehrenfeucht","year":"1994","unstructured":"A. Ehrenfeucht, H. Gabow, R. McConnell, S. Sullyvan, An O(n2) Divide-and-Conquer Algorithms for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs, Journal of Algorithms, 16 (1994), pp. 283\u2013294.","journal-title":"Journal of Algorithms"},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/65950.65951","volume":"36","author":"C. Gabor","year":"1989","unstructured":"C. Gabor, K. Supowit, W. Hsu, Recognizing Circle Graphs in Polynomial Time, Journal of the. ACM, 36 (1989), pp. 435\u2013473.","journal-title":"Journal of the. ACM"},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"P. Hammer","year":"1990","unstructured":"P. Hammer, F. Maffray, Completely Separable Graphs, Discrete Applied Mathematics, 27 (1990), pp. 85\u201399.","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR13","first-page":"150","volume":"29","author":"P. Klein","year":"1988","unstructured":"P. Klein, Efficient Parallel Algorithms for Chordal Graphs, 29. IEEE-FOCS (1988), S. 150\u2013161.","journal-title":"IEEE-FOCS"},{"key":"15_CR14","unstructured":"R. McConnell, J. Spinrad, Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs, Fifth Annual ACM-SIAM Symposium of Discrete Algorithms (1994), pp. 536\u2013545."},{"key":"15_CR15","unstructured":"G. Miller, J. Reif, Parallel Tree Contraction and its Application, 26. IEEE-FOCS (1985), pp. 478\u2013489."},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/58562.59300","volume":"36","author":"J.H. Muller","year":"1989","unstructured":"J.H. Muller, J. Spinrad, Incremental Modular Decomposition, Journal of the ACM, 36 (1989), pp. 1\u201319.","journal-title":"Journal of the ACM"},{"key":"15_CR17","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"J. Spinrad, On Comparability and Permutation Graphs, SIAM-Journal on Computing, 14 (1985), pp. 658\u2013670.","journal-title":"SIAM-Journal on Computing"},{"key":"15_CR18","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0166-218X(92)90180-I","volume":"39","author":"J. Spinrad","year":"1992","unstructured":"J. Spinrad, P4-Trees and Substitution Decomposition, Discrete Applied Mathematics, 39 (1992), pp. 263\u2013291.","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J. Spinrad","year":"1994","unstructured":"J. Spinrad, Recognition of Circle Graphs, Journal of Algorithms, 16 (1994), pp. 264\u2013282.","journal-title":"Journal of Algorithms"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. Tarjan","year":"1984","unstructured":"R. Tarjan, U. Vishkin, Finding Biconnected Components in Logarithmic Parallel Time, SIAM-Journal on Computing, 14 (1984), pp. 862\u2013874.","journal-title":"SIAM-Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_123.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:37:20Z","timestamp":1742596640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_123","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}