{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:38Z","timestamp":1725664238009},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583387"},{"type":"electronic","value":"9783540486633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58338-6_78","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:49:41Z","timestamp":1330253381000},"page":"316-325","source":"Crossref","is-referenced-by-count":7,"title":["On parallel complexity of maximum f-matching and the degree sequence problem"],"prefix":"10.1007","author":[{"given":"Anders","family":"Dessmark","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oscar","family":"Garrido","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Takao Asano. Graphical Degree Sequence Problems with Connectivity Requirements. Proc. ISAAC'93, Hong Kong, Springer, LNCS 762, pp. 88\u201397.","DOI":"10.1007\/3-540-57568-5_233"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. Israeli, Y. Shiloach. Finding Euler circuits in logarithmic parallel time. Proc. STOC, 1984, pp. 249\u2013257.","DOI":"10.1145\/800057.808688"},{"key":"24_CR3","volume-title":"Graphs and hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge. Graphs and hypergraphs. North-Holland, American Elsevier, Amsterdam-London-New York (1973)."},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"E. Cohen. Approximate max flow on small depth networks. Proc. 33rd FOCS, 1992, pp. 648\u2013658.","DOI":"10.1109\/SFCS.1992.267786"},{"key":"24_CR5","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 J. Computing, 17, (1988), pp. 770\u2013785.","journal-title":"SIAM J. Computing"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"K. Diks, O. Garrido, A. Lingas. Parallel algorithms for finding maximal k-dependent sets and maximal f-matchings. Proc. ISA 91, Taipei, Springer, LNCS 557, pp. 385\u2013395.","DOI":"10.1007\/3-540-54945-5_82"},{"key":"24_CR7","first-page":"139","volume":"11","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s and T. Gallai. Graphs with prescribed degrees. Mat. Lapok 11, 1960, pp. 139\u2013144.","journal-title":"Mat. Lapok"},{"key":"24_CR8","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02122800","volume":"8","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and V. Pan. Improved processor bounds for combinatorial problems in RNC. Combinatorica, 8, 1988, pp. 189\u2013200.","journal-title":"Combinatorica"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"M. Goldberg, T. Spencer. A new parallel algorithm for the maximal independent set problem. Proc. 28th FOCS, 1987.","DOI":"10.1109\/SFCS.1987.2"},{"issue":"4","key":"24_CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02579264","volume":"6","author":"H.J. Karloff","year":"1986","unstructured":"H.J. Karloff. A Las Vegas RNC algorithm for maximum matching. Combinatorica 6(4), pp. 387:391, 1986.","journal-title":"Combinatorica"},{"key":"24_CR11","first-page":"869","volume-title":"Handbook of Theoretical Computer Science, Vol. A","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared memory machines. In: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, Vol. A (Elsevier Science Publishers, Amsterdam, 1990) 869\u2013941."},{"issue":"1","key":"24_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"R.M. Karp, E. Upfal, and A. Wigderson. Constructing a Maximum Matching is in Random NC. Combinatorica, 6(1), (1986) pp. 35\u201348.","journal-title":"Combinatorica"},{"key":"24_CR13","unstructured":"A. Maheshwari. Personal communication."},{"key":"24_CR14","unstructured":"S. Micali and V.V. Vazirani. An O(\u221a\u00a6V\u2225E\u00a6) Algorithm for Finding Maximum Matching in General Graphs. Proc. 21st FOCS (1980), pp. 17\u201327."},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, U.V. Vazirani, and V.V. Vazirani. Matching is as easy as matrix inversion. Combinatorica 7(1), pp. 105\u2013113.","DOI":"10.1007\/BF02579206"},{"key":"24_CR16","doi-asserted-by":"crossref","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"W.T. Tutte. A Short Proof of the Factor Theorem for Finite Graphs. Canad. J. Math 6, 1954, pp. 347\u2013352.","journal-title":"Canad. J. Math"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1994"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58338-6_78.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:19:50Z","timestamp":1605629990000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58338-6_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583387","9783540486633"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-58338-6_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}