{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:54:45Z","timestamp":1725573285287},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_30","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T06:34:15Z","timestamp":1149230055000},"page":"308-319","source":"Crossref","is-referenced-by-count":1,"title":["A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small"],"prefix":"10.1007","author":[{"given":"Raghav","family":"Kulkarni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/0022-0000(92)90005-4","volume":"44","author":"E. Dahlhouse","year":"1992","unstructured":"Dahlhouse, E., Karpinski, M.: Perfect matching for regular graphs is AC 0-hard for the general matching problem. J. Comput. Syst. Sci.\u00a044, 94\u2013102 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanent is in NC. In: Proceedings of 28th IEEE Conference on Foundations of Computer Science, pp. 166\u2013172. IEEE Computer Society Press, Los Alamitos (1987)","DOI":"10.1109\/SFCS.1987.56"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Kulkarni, R., Mahajan, M.: Seeking a vertex of the planar matching polytope in NC. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 472\u2013483. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30140-0_43"},{"key":"30_CR4","unstructured":"Karpinski, M., Rytter, W.: Fast parallel algorithms for graph matching problems. Oxford Science Publications (1998)"},{"key":"30_CR5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"Karp, R., Upful, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica\u00a06, 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"30_CR6","unstructured":"Lovasz, Plummer: Matching theory. Mathematical Studies, Annals of Discrete Maths, vol.\u00a025. North-Holland, Amsterdam (1986)"},{"key":"30_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"30","author":"G. Lev","year":"1981","unstructured":"Lev, G., Pippenger, M., Valiant, L.: A fast parallel algorithm for routing in permutation networks. IEEE Transactions on Computers\u00a0C-30, 93\u2013100 (1981)","journal-title":"IEEE Transactions on Computers C-"},{"key":"30_CR8","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G. Milller","year":"1995","unstructured":"Milller, G., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM Journal of Computing\u00a024, 1002\u20131017 (1995)","journal-title":"SIAM Journal of Computing"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.: A new NC algorithm to find a perfect matching in planar and bounded genus graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351\u2013357 (2000)","DOI":"10.1145\/335305.335346"},{"issue":"1","key":"30_CR10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as easy as matrix inversion. Combinatorica\u00a07(1), 105\u2013131 (1987)","journal-title":"Combinatorica"},{"issue":"3","key":"30_CR11","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1137\/S0097539796299266","volume":"28","author":"A. Schrijver","year":"1998","unstructured":"Schrijver, A.: Bipartite Edge Coloring in O(Delta m) Time. SIAM J. Comput.\u00a028(3), 841\u2013846 (1998)","journal-title":"SIAM J. Comput."},{"key":"30_CR12","unstructured":"Sharan, R., Wigderson, A.: A new NC algorithm for perfect matching in cubic bipartite graphs. In: Proc. of ISTCS 1996, pp. 56\u201365 (1996)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:04:26Z","timestamp":1619492666000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/11758471_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}