{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:58Z","timestamp":1725663298741},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540171799"},{"type":"electronic","value":"9783540472391"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-17179-7_24","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:08:16Z","timestamp":1330178896000},"page":"394-411","source":"Crossref","is-referenced-by-count":2,"title":["Connectivity algorithms using rubber bands"],"prefix":"10.1007","author":[{"given":"Laszlo","family":"Lovasz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"D.Coppersmith and S.Winograd (1982), On the asymptotic complexity of matrix multiplication, SIAM J. Computing, 472\u2013492.","DOI":"10.1137\/0211038"},{"key":"24_CR2","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","volume":"5","author":"L. Csanky","year":"1976","unstructured":"L. Csanky (1976), Fast parallel matrix inversion algorithms, SIAM J. Computing 5, 618\u2013623.","journal-title":"SIAM J. Computing"},{"key":"24_CR3","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds (1967), Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B 71B, 241\u2013247.","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"key":"24_CR4","unstructured":"S.Even (1979), Graph algorithms, Computer Science Press."},{"key":"24_CR5","first-page":"274","volume":"XVIII","author":"G. Frobenius","year":"1917","unstructured":"G. Frobenius (1917), \u00dcber zerlegbare Determinanten, Sitzungsber. K\u00f6nigl. Preuss. Akad. Wiss. XVIII, 274\u2013277.","journal-title":"Sitzungsber. K\u00f6nigl. Preuss. Akad. Wiss."},{"key":"24_CR6","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0209016","volume":"9","author":"Z. Galil","year":"1980","unstructured":"Z. Galil (1980), Finding the vertex connectivity of graphs, SIAM J. Computing, 9, 197\u2013199.","journal-title":"SIAM J. Computing"},{"key":"24_CR7","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lovasz and A. Schrijver (1981), The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, 169\u2013197.","journal-title":"Combinatorica"},{"key":"24_CR8","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"M. Gr\u00f6tschel, L. Lovasz and A. Schrijver (1984), Polynomial algorithms for perfect graphs, Annals of Discrete Math. 21, 325\u2013256.","journal-title":"Annals of Discrete Math."},{"key":"24_CR9","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0095-8956(73)90031-2","volume":"B15","author":"A. W. Ingleton","year":"1973","unstructured":"A.W. Ingleton and M.J. Piff (1973), Gammoids and transversal matroids, J. Comb. Theory B15, 51\u201368.","journal-title":"J. Comb. Theory"},{"key":"24_CR10","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 (1986), Constructing a perfect matching is in random NC, Combinatorica 6, 35\u201348.","journal-title":"Combinatorica"},{"key":"24_CR11","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P. W. Kasteleyn","year":"1961","unstructured":"P.W. Kasteleyn (1961), The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica 27, 1209\u20131225.","journal-title":"Physica"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"N.Linial, L.Lovasz and A.Wigderson (1986a), A physical interpretation of graph connectivity, Proc. 27th Annual Symp. on Found. of Computer Science, IEEE Computer Soc.","DOI":"10.1109\/SFCS.1986.3"},{"key":"24_CR13","unstructured":"N.Linial, L.Lovasz and A.Wigderson (1986b), Rubber bands, convex embeddings, and graph connectivity, Combinatorica (submitted)."},{"key":"24_CR14","first-page":"565","volume-title":"Fundamentals of Computation Theory, FTC' 79","author":"L. Lova'sz","year":"1979","unstructured":"L. Lova'sz (1979a), On determinants, matchings, and random algorithms, in: Fundamentals of Computation Theory, FTC' 79 (ed. L. Budach), Akademie-Verlag, Berlin; 565\u2013574."},{"key":"24_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lovasz","year":"1979","unstructured":"L. Lovasz (1979b), On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25, 1\u20137.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"24_CR16","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"L. Lovasz and M.D. Plummer (1986), Matching Theory, Akad\u0117miai Kiado, Budapest-North-Holland, Amsterdam."},{"key":"24_CR17","unstructured":"L.Lovasz, M.Saks and A.Schrijver, Connectivity and orthonormal representations of graphs (to be published)"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"K.Mulmuley, U.Vazirani and V.Vazirani (1986), Matching is as easy as matric inversion, Combinatorica (to appear)","DOI":"10.1145\/28395.383347"},{"key":"24_CR19","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/qmath\/17.1.303","volume":"17","author":"H. Perfect","year":"1966","unstructured":"H. Perfect (1966), Symmetrized form of P.Hall's theorem on distinct representatives, Quart. J. Math. Oxford 17, 303\u2013306.","journal-title":"Quart. J. Math. Oxford"},{"key":"24_CR20","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J.T. Schwartz (1980), Fast probabilistic algorithms for verification of polynomial identities, J. ACM 27, 701\u2013717.","journal-title":"J. ACM"},{"key":"24_CR21","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W. T. Tutte","year":"1947","unstructured":"W.T. Tutte (1947), The factorization of linear graphs, J. London. Math. Soc. 22, 107\u2013111.","journal-title":"J. London. Math. Soc."},{"key":"24_CR22","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W. T. Tutte","year":"1963","unstructured":"W.T. Tutte (1963), How to draw a graph, Proc. London Math. Soc. 13, 743\u2013768.","journal-title":"Proc. London Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-17179-7_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:12:24Z","timestamp":1605625944000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-17179-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540171799","9783540472391"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-17179-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}