{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:05Z","timestamp":1725663485366},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540518594"},{"type":"electronic","value":"9783540468318"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51859-2_22","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:18:56Z","timestamp":1330204736000},"page":"274-308","source":"Crossref","is-referenced-by-count":2,"title":["Optimal parallel algorithms for b-matchings in trees"],"prefix":"10.1007","author":[{"given":"Constantine N. K.","family":"Osiakwan","sequence":"first","affiliation":[]},{"given":"Selim G.","family":"Akl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"22_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., J.E. Hopcroft and J.D. Ullman, [1974], The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974."},{"key":"22_CR2","volume-title":"The Design and Analysis of Parallel Algorithms","author":"S.G. Akl","year":"1989","unstructured":"Akl, S.G., [1989], The Design and Analysis of Parallel Algorithms, Prentice Hall, Englewood Cliffs, New Jersey, 1989."},{"key":"22_CR3","volume-title":"Parallel Sorting Algorithms","author":"S.G. Akl","year":"1985","unstructured":"Akl, S.G., [1985], Parallel Sorting Algorithms, Academic Press, Orlando, Florida, 1985."},{"issue":"1","key":"22_CR4","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0020-0190(84)90128-5","volume":"19","author":"S.G. Akl","year":"1984","unstructured":"Akl, S.G., [1984], \"An Optimal Algorithm for Parallel Selection\", Information Processing Letters, Vol. 19, No. 1, 1984, pp. 47\u201350.","journal-title":"Information Processing Letters"},{"key":"22_CR5","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C. [1973], Graphs and Hypergraphs, (translated by E. Minieka) North-Holland, New York, New York, 1973."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., R.W. Floyd, V. Pratt, R.L. Rivest and R.E. Tarjan, [1973], \"Time Bounds for Selection\", Journal of Computer and System Sciences, Vol. 7, 1973, pp. 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"Bondy, J.A. and U.S.R. Murty, [1976], Graph Theory with Applications, North-Holland, New York, New York, 1976."},{"issue":"2","key":"22_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"Brent, R.P., [1974], \"The Parallel Evaluation of General Arithmetic Expressions\", Journal of the Association for Computing Machinery, Vol. 21, No. 2, April 1974, pp. 201\u2013206.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"22_CR9","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"Cole, R. and U. Vishkin, [1988], \"Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal List Ranking in Logarithmic Time\", SIAM Journal on Computing, Vol. 17, No. 1, February 1988, pp. 128\u2013142.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Cole, R. and U. Vishkin, [1986], \"Approximate Parallel and Exact Parallel Scheduling with Applications to Lists, Tree and Graph Problems\", Proceedings of the IEEE 27\n\n                  th\n                \nSymposium on Foundations of Computer Science, October 27\u201329, 1986, pp. 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"issue":"3","key":"22_CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J., [1965a], \"Paths, Trees and Flowers\", Canadian Journal of Mathematics Vol. 17, No. 3, 1965, pp. 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"issue":"1and2","key":"22_CR12","first-page":"125","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J., [1965b], \"Matching and Polyhedrons with 0,1 Vertices\", Journal of Research of the National Bureau of Standards B. Mathematics and Mathematical Physics Vol. 69B, Nos. 1 and 2, Jan.\u2013June 1965, pp. 125\u2013130.","journal-title":"Mathematics and Mathematical Physics"},{"issue":"2","key":"22_CR13","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H.N. Gabow","year":"1976","unstructured":"Gabow, H.N., [1976], \"An Efficient Implementation of Edmonds Algorithm for Maximal Matching on Graphs\", Journal of the Association for Computing Machinery, Vol. 23, No. 2, April 1976, pp. 221\u2013234.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"22_CR14","volume-title":"Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs","author":"H.N. Gabow","year":"1974","unstructured":"Gabow, H.N., [1974], \"Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs\", Ph.D. Dissertation, Department of Computer Science, Stanford University, Stanford, California, 1974."},{"issue":"1","key":"22_CR15","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0205009","volume":"5","author":"S. Goodman","year":"1976","unstructured":"Goodman, S., S. Hedetniemi and R.E. Tarjan, [1976], \"b-Matchings in Trees\", SIAM Journal on Computing, Vol. 5, No. 1, March 1976, pp. 104\u2013108.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0196-6774(88)90007-7","volume":"9","author":"X. He","year":"1988","unstructured":"He, X. and Y. Yesha, [1988], \"Binary Algebraic Computation and Parallel Algorithms for Simple Graphs\", Journal of Algorithms, Vol. 9, 1988, pp. 92\u2013113.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"22_CR17","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1137\/0205010","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"Hyafil, L., [1976], \"Bounds for Selection\", SIAM Journal on Computing, Vol. 5, No. 1, March 1976, pp. 109\u2013114.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR18","volume-title":"The Art of Computer Programming, Vol. I: Fundamental Algorithms","author":"D.E. Knuth","year":"1976","unstructured":"Knuth, D.E., [1976], The Art of Computer Programming, Vol. I: Fundamental Algorithms. Addison-Wesley, Reading, Massachusetts, 1968."},{"key":"22_CR19","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L. [1976], Combinatorial Optimization: Networks and Matroids, Holt-Rinehart-Winston, New York 1976."},{"key":"22_CR20","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H. and K Steiglitz, [1982], Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, New Jersey, 1982."},{"key":"22_CR21","unstructured":"Pawagi, S., [1987], \"Parallel Algorithms for Maximum Weight Matching in Trees\", Proceedings of the 1987 International Conference on Parallel Processing, Aug 12\u201321 1987, pp. 204\u2013206."},{"key":"22_CR22","first-page":"12","volume-title":"Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E. and U. Vishkin, [1984], \"Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary)\", Proceedings of the 25\n\n                  th\n                \nAnnual IEEE Symposium on Foundation of Computer Science, IEEE, New York, 1984, pp. 12\u201320."},{"issue":"2","key":"22_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E. [1972], \"Depth-First Search and Linear Graph Algorithms\", SIAM Journal on Computing, Vol. 1, No. 2, June 1972, pp. 146\u2013160.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Optimal Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51859-2_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:05:55Z","timestamp":1619571955000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51859-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540518594","9783540468318"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-51859-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}