{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:18Z","timestamp":1725467898558},"publisher-location":"Berlin\/Heidelberg","reference-count":10,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040382","type":"book-chapter","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T20:03:50Z","timestamp":1154549030000},"page":"139-148","source":"Crossref","is-referenced-by-count":2,"title":["Computing a perfect matching in a line graph"],"prefix":"10.1007","author":[{"given":"Joseph","family":"Naor","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Marek Chrobak and Joseph Naor, \u201cPerfect Matchings in Claw Free Graphs\u201d, In preparation."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/1385-7258(73)90007-3","volume":"35","author":"G. Chartrand","year":"1973","unstructured":"G. Chartrand, A. D. Polimeni and M. James Stewart, \u201cThe Existance of 1-Factors in Line Graphs, Squares and Total Graphs\u201d, Indag. Math. 35, pp. 228\u2013232 (1973).","journal-title":"Indag. Math."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"D. Y. Grigoriev and M. Karpinski, \u201cThe Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC\u201d, 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, 1987.","DOI":"10.1109\/SFCS.1987.56"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"M. Goldberg and T. Spencer, \u201cA New Parallel Algorithm for the Maximal Independent Set Problem\u201d, 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, 1987.","DOI":"10.1109\/SFCS.1987.2"},{"issue":"1","key":"15_CR5","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, \u201cConstructing a Perfect Matching is in Random NC\u201d, Combinatorica, Vol. 6, 1, pp. 35\u201348, (1986).","journal-title":"Combinatorica"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0196-6774(88)90006-5","volume":"9","author":"M. Karchmer","year":"1988","unstructured":"Mauricio Karchmer and Joseph Naor, \u201cA Fast Parallel Algorithm for Coloring a Graph with \u0394 Colors\u201d, Journal of Algorithms, Vol. 9, 1, pp. 83\u201391, (1988).","journal-title":"Journal of Algorithms"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"M. Luby, \u201cA simple parallel algorithm for the maximal independent set\u201d, Siam Journal on Computing, Vol. 15, 4, (1986).","DOI":"10.1137\/0215074"},{"issue":"1","key":"15_CR8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. V. Vazirani and V. V. Vazirani, \u201cMatching is as easy as Matrix Inversion\u201d, Combinatorica, Vol. 7, 1, pp. 105\u2013113, (1987).","journal-title":"Combinatorica"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Petersen","year":"1891","unstructured":"J. Petersen, \u201cDie Theorie der Regul\u00e4ren Graphs\u201d, Acta Math. Vol. 15, pp. 193\u2013220 (1891).","journal-title":"Acta Math."},{"key":"15_CR10","series-title":"Lecture Notes in Math.","first-page":"350","volume-title":"On Tutte's Factorization Theorem\u201d, Proceedings of the Capital Conference on Graph Theory and Combinatorics","author":"D. P. Sumner","year":"1973","unstructured":"D. P. Sumner, \u201cOn Tutte's Factorization Theorem\u201d, Proceedings of the Capital Conference on Graph Theory and Combinatorics, George Washington University, Washington D.C., 1973, pp. 350\u2013355. Lecture Notes in Math., Vol. 406, Springer, Berlin, 1974."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040382.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:40:15Z","timestamp":1607532015000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0040382","relation":{},"subject":[]}}