{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:25Z","timestamp":1725664045022},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_55","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:40:35Z","timestamp":1330263635000},"page":"225-236","source":"Crossref","is-referenced-by-count":0,"title":["The parallel complexity of elimination ordering procedures"],"prefix":"10.1007","author":[{"given":"Elias","family":"Dahlhaus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0304-0208(08)72923-2","volume-title":"Topics on Perfect Graphs","author":"V. Chvatal","year":"1984","unstructured":"V. Chvatal, Perfectly Ordered Graphs, Topics on Perfect Graphs, C. Berge, V. Chvatal eds., North Holland, Amsterdam(1984), pp. 63\u201365."},{"key":"20_CR2","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1002\/jgt.3190110405","volume":"11","author":"V. Chvatal","year":"1987","unstructured":"V. Chvatal, C. Hoang, N. Mahadev, D. de Werra, Four Classes of Perfectly orderable Graphs, Journal of Graphs Theory 11 (1987), pp. 481\u2013495.","journal-title":"Journal of Graphs Theory"},{"key":"20_CR3","unstructured":"R. Cole, Parallel Merge Sort, 27. IEEE-FOCS (1986), pp. 511\u2013516."},{"key":"20_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook, A Taxonomy of Problems with Fast Parallel Algorithms, Information and Control 64 (1985), pp. 2\u201322.","journal-title":"Information and Control"},{"key":"20_CR5","unstructured":"E. Dahlhaus, Chordale Graphen im besonderen Hinblick auf parallele Algorithmen, Habilitation thesis, 1991, University of Bonn."},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"M. Farber, Characterizations of Strongly Chordal Graphs, Discrete Mathematics 43 (1983), pp. 173\u2013189.","journal-title":"Discrete Mathematics"},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. Fulkerson","year":"1965","unstructured":"D. Fulkerson, O. Gross, Incidence Matrices and Interval Graphs, Pacific Journal of Mathematics 15 (1965), pp.835\u2013855.","journal-title":"Pacific Journal of Mathematics"},{"key":"20_CR8","volume-title":"Efficient Parallel Algorithms","author":"A. Gibbons","year":"1989","unstructured":"A. Gibbons, W. Rytter, Efficient Parallel Algorithms, Cambridge University Press, Cambridge, 1989."},{"key":"20_CR9","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg, T. Spencer, Constructing a Maximal Independent Set in Parallel, SIAM Journal on Discrete Mathematics 2 (1989), pp. 322\u2013328.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"20_CR10","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/0196-8858(88)90019-X","volume":"9","author":"B. Jamison","year":"1988","unstructured":"B. Jamison, S. Olariu, On tie Semi-Perfect Elimination, Advances in Applied Mathematics 9 (1988), pp. 364\u2013376.","journal-title":"Advances in Applied Mathematics"},{"key":"20_CR11","unstructured":"P. Klein, Efficient Parallel Algorithms for Chordal Graphs, 29. IEEE-FOCS (1988), pp. 150\u2013161."},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"854","DOI":"10.1137\/0216057","volume":"16","author":"A. Lubiw","year":"1987","unstructured":"A. Lubiw, Doubly Lexical Orderings of Matrices, SIAM Journal on Computing 16 (1987), pp. 854\u2013879","journal-title":"SIAM Journal on Computing"},{"key":"20_CR13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0012-365X(90)90251-C","volume":"80","author":"M. Middendorf","year":"1990","unstructured":"M. Middendorf, F. Pfeiffer, On the Complexity of Recognizing Perfectly Orderable Graphs, Discrete Mathematics 80 (1990), pp. 327\u2013333.","journal-title":"Discrete Mathematics"},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02088292","volume":"22","author":"S. Miyano","year":"1989","unstructured":"S. Miyano, The Lexicographically First Maximal Subgraph Problems: P-Completeness and NC-Algorithms, Mathematical Systems Theory 22 (1989), pp. 47\u201373.","journal-title":"Mathematical Systems Theory"},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"R. Paige, R. Tarjan, Three Partition Refinement Algorithms, SIAM Journal on Computing 16 (1987), pp. 973\u2013989.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR16","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. Rose","year":"1970","unstructured":"D. Rose, Triangulated Graphs and the Elimination Process, Journal of Mathematical Analysis and Applications 32 (1970), pp. 597\u2013609.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"20_CR17","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"D. Rose, R. Tarjan, G. Lueker, Algorithmic Aspects on Vertex Elimination on Graphs, SIAM Journal on Computing 5 (1976), pp. 266\u2013283.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR18","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach, U. Vishkin, An O(log n) Parallel Connectivity Algorithm, Journal of Algorithms 3 (1982), pp. 57\u201367.","journal-title":"Journal of Algorithms"},{"key":"20_CR19","unstructured":"J. Spinrad, Doubly Lexical Ordering for Dense 0\u20131 Matrices, to appear."},{"key":"20_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"},{"key":"20_CR21","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R. Tarjan","year":"1984","unstructured":"R. Tarjan, M. Yannakakis, Simple Linear Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing 13 (1984), pp. 566\u2013579. Addendum: SIAM Journal on Computing 14 (1985), pp. 254\u2013255.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR22","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"D. Welsh","year":"1967","unstructured":"D. Welsh, M. Powell, An Upper Bound on the Chromatic Number of a Graph and its Application to Timetabling Problems, Computer Journal 10 (1967), pp. 85\u201387.","journal-title":"Computer Journal"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:09:37Z","timestamp":1619572177000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}