{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:19Z","timestamp":1725663319911},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_13","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:06:07Z","timestamp":1330185967000},"page":"147-162","source":"Crossref","is-referenced-by-count":5,"title":["Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs"],"prefix":"10.1007","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]},{"given":"Mark B.","family":"Novick","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"M.Ben-Or and P.Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, Proc. 20th Symposium on Theory on Computing, 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Paths, trees and flowers, Canad. J. Math. 17 (1965) 449\u2013467.","journal-title":"Canad. J. Math."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"D. Y. Grigoriev and M. Karpi\u0144ski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, CA, 1987, pp. 166\u2013172.","DOI":"10.1109\/SFCS.1987.56"},{"key":"13_CR4","unstructured":"F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1972."},{"key":"13_CR5","unstructured":"Xin He, Private communication."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D.S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 6 (1985) 434\u2013451.","journal-title":"J. Algorithms"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","volume":"8","author":"D. S. Johnson","year":"1987","unstructured":"D.S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 8 (1987) 438\u2013448.","journal-title":"J. Algorithms"},{"issue":"1","key":"13_CR8","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 perfect matching is in random NC, Combinatorica 6, 1 (1986) 35\u201348.","journal-title":"Combinatorica"},{"key":"13_CR9","first-page":"257","volume":"17","author":"M. Vergnas Las","year":"1975","unstructured":"M. Las Vergnas, A note on matchings in graphs, Colloque sur la Th\u00e9orie des Graphes (Paris 1974), Cahiers Centre Etudes Rech. Op\u00e9r. 17, 1975, 257\u2013260.","journal-title":"Cahiers Centre Etudes Rech. Op\u00e9r."},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1145\/321850.321853","volume":"21","author":"P. G. H. H. Lehot","year":"1974","unstructured":"P. G. H. Lehot, An optimal algorithm to detect a line graph and output its root graph, JACM\n21, (1974) pp. 569\u2013575.","journal-title":"JACM"},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G. J. Minty","year":"1980","unstructured":"G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory B 28 (1980) 284\u2013304.","journal-title":"J. Comb. Theory B"},{"key":"13_CR12","unstructured":"G.Miller and J.Naor, Flow in planar graphs with multiple sources and sinks, manuscript."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. Reif, Parallel tree contraction and its applications, Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science, (1985) pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"issue":"1","key":"13_CR14","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, Matching is as easy as matrix inversion, Combinatorica 7, 1 (1987) 105\u2013113.","journal-title":"Combinatorica"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"J. Naor, Computing a perfect matching in a line graph, 3rd International Workshop on Parallel Computation and VLSI Theory, Aegean Workshop on Computing, Corfu Island, Greece (1988).","DOI":"10.1007\/BFb0040382"},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N. D. Roussopoulos","year":"1973","unstructured":"N. D. Roussopoulos, A max { m, n } algorithm for determining the graph H from its line graph G, Information Processing Letters\n2 (1973) pp. 108\u2013112.","journal-title":"Information Processing Letters"},{"key":"13_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N. Sbihi","year":"1980","unstructured":"N. Sbihi, Algorithme de recherche d'un stable de cardinalit\u00e9 maximum dans un graphe, Disc. Math. 29 (1980) 53\u201376.","journal-title":"Disc. Math."},{"key":"13_CR18","series-title":"Lecture Notes in Math.","first-page":"350","volume-title":"Proceedings of the Capital Conference on Graph Theory and Combinatorics","author":"D. P. Summer","year":"1973","unstructured":"D. P. Summer, On Tutte's factorization theorem, 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."},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, An O(log n) parallel connectivity algorithm, J. Algorithms\n3 (1982) 57\u201367.","journal-title":"J. Algorithms"},{"key":"13_CR20","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H. Whitney","year":"1932","unstructured":"H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math.\n54 (1932), 150\u2013168.","journal-title":"Amer. J. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:04:32Z","timestamp":1619557472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}