{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T14:37:36Z","timestamp":1648823856397},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,4,1]],"date-time":"1995-04-01T00:00:00Z","timestamp":796694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,4]]},"DOI":"10.1007\/bf01293484","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T03:39:41Z","timestamp":1111721981000},"page":"346-356","source":"Crossref","is-referenced-by-count":2,"title":["Random parallel algorithms for finding exact branchings, perfect matchings, and cycles"],"prefix":"10.1007","volume":"13","author":[{"given":"D.","family":"Bruschi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Ravasio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0166-218X(87)90067-9","volume":"16","author":"F. Barahona","year":"1987","unstructured":"Barahona, F., and W. R. Pulleyblank, Exact arborescences, matchings and cycles,Discrete Appl. Math.,16 (1987), 91?99.","journal-title":"Discrete Appl. Math."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"Borodin, A., S. A. Cook, and N. Pippenger, Parallel computation for well-endowed rings and space bounded probabilistic machines,Inform, and Control,58 (1983), 113?136.","journal-title":"Inform, and Control"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0196-6774(92)90018-8","volume":"13","author":"P. M. Camerini","year":"1992","unstructured":"Camerini, P. M., G. Galbriati, and F. Maffioli, Random pseudo-polynomial algorithms for exact matroid problem.J. Algorithms,13 (1992), 258?273.","journal-title":"J. Algorithms"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"Cook, S., A taxonomy of problems which have fast parallel algorithms,Inform, and Control,64 (1985), 2?22.","journal-title":"Inform, and Control"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J., Optimum branchings,J. Res. Nat. Bur. Standards,71B (1967), 233?240.","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Galbiati, G., and F. Maffioli, Constructing an exact parity base is in RNC2, Report No. 91-022, Dip. di Elettronica, Polit, di Milano, 1991.","DOI":"10.1142\/S0129626492000441"},{"key":"CR7","volume-title":"The Numerical Treatment of Single Nonlinear Equations","author":"A. S. Householder","year":"1970","unstructured":"Householder, A. S.,The Numerical Treatment of Single Nonlinear Equations, McGrawHill, New York, 1970."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/321864.321868","volume":"22","author":"E. Horowitz","year":"1975","unstructured":"Horowitz, E., and S. Sahni, On computing the exact determinant of matrices with polynomial entries,J. Assoc. Comput. Mack,22 (1975), 38?50.","journal-title":"J. Assoc. Comput. Mack"},{"key":"CR9","first-page":"497","volume":"72","author":"G. Kirchhoff","year":"1947","unstructured":"Kirchhoff, G., \ufffdber die Ausfl\ufffdsung der Gleichungen auf welche man bei der Untersuchungen der Linearen Verteilung Galvanisher Str\ufffdme gef\ufffdrt wird,Poggendorf Ann. Phys.,72 (1947), 497?508.","journal-title":"Poggendorf Ann. Phys."},{"key":"CR10","first-page":"869","volume-title":"Handbook of Theoretical Computer Science, vol. A","author":"R. M. Karp","year":"1990","unstructured":"Karp, R. M., and V. Ramachandran, A survey of parallel algorithms for shared-memory machines, in: J. van Leeuwen, ed.,Handbook of Theoretical Computer Science, vol. A, North-Holland, Amsterdam, 1990, pp. 869?941."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0022-0000(88)90027-X","volume":"36","author":"R. M. Karp","year":"1988","unstructured":"Karp, R. M., E. Upfal, and A. Widgerson, The complexity of parallel search,J. Comput. System Sci.,36 (1988), 225?253.","journal-title":"J. Comput. System Sci."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Lov\ufffdsz, L., Computing ears and branchings in parallel,Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 464?467.","DOI":"10.1109\/SFCS.1985.16"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., U. V. Vazirani, and V. V. Vazirani, Matching is as easy as matrix inversion,Combinatorica,7 (1987), 105?113.","journal-title":"Combinatorica"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/322307.322309","volume":"29","author":"C. H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C. H., and M. Yannakakis, The complexity of restricted spanning tree problems,J. Assoc. Comput. Mach.,29 (1982), 285?309.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. H. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C. H., and M. Yannakakis, The complexity of facets (and some facets of complexity),J. Comput. System Sci.,28 (1984), 244?259.","journal-title":"J. Comput. System Sci."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"C. Schnorr","year":"1980","unstructured":"Schnorr, C., On self-transformable combinatorial problems,J. Assoc. Comput. Mach.,27 (1980), 701?717.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W. T. Tutte","year":"1947","unstructured":"Tutte, W. T., The factorization of linear graphs,J. London Math. Soc.,22 (1947), 107?111.","journal-title":"J. London Math. Soc."},{"key":"CR18","volume-title":"Graph Theory","author":"W. T. Tutte","year":"1984","unstructured":"Tutte, W. T.,Graph Theory, Addison-Wesley, Reading, MA, 1984."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. G. Valiant","year":"1976","unstructured":"Valiant, L. G., Relative complexity on checking and evaluating,Inform. Process. Lett.,5 (1976), 20?23.","journal-title":"Inform. Process. Lett."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"V. V. Vazirani","year":"1989","unstructured":"Vazirani, V. V., NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems,Inform. and Comput.,80 (1989), 152?163.","journal-title":"Inform. and Comput."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. W. Wagner","year":"1987","unstructured":"Wagner, K. W., More complicated questions about maxima and minima, and some closures of NP,Theoret. Comput. Sci.,51 (1987), 53?80.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293484.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293484\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:48:30Z","timestamp":1586180910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,4]]}},"alternative-id":["BF01293484"],"URL":"https:\/\/doi.org\/10.1007\/bf01293484","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,4]]}}}