{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:57:22Z","timestamp":1725663442741},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562870"},{"type":"electronic","value":"9783540475071"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56287-7_111","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:01:39Z","timestamp":1330254099000},"page":"265-278","source":"Crossref","is-referenced-by-count":1,"title":["Fast sequential and randomised parallel algorithms for rigidity and approximate min k-cut"],"prefix":"10.1007","author":[{"given":"Sachin","family":"Patkar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Narayanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"20_CR1","unstructured":"Crapo, H.: On the Generic Rigidity of Plane Frameworks, Research Report, No. 1278, INRIA, 1990."},{"key":"20_CR2","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"4","author":"A. Frank","year":"1988","unstructured":"Frank, A. and Tardos, E.: Generalized Polymatroids and Submodular Flows, Mathematical Programming, vol. 4, 1988, pp. 489\u2013565.","journal-title":"Mathematical Programming"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Gabow, H.N. and Westermann, H.H.: Forests, Frames and Games: Algorithms for Matroid sums and Applications, in Proc. 20 th STOC, 1988, pp. 407\u2013421.","DOI":"10.1145\/62212.62252"},{"issue":"No.1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/0221008","volume":"21","author":"B. Hendrickson","year":"1992","unstructured":"Hendrickson, B.: Conditions for Unique Graph Realizations, SIAM J. Computing, vol. 21, No. 1, 1992, pp. 65\u201384.","journal-title":"SIAM J. Computing"},{"key":"20_CR5","first-page":"186","volume":"26","author":"H. Imai","year":"1983","unstructured":"Imai, H.: Network flow algorithms for lower truncated transversal polymatroids, J. of the Op. Research Society of Japan, vol. 26, 1983, pp. 186\u2013210.","journal-title":"J. of the Op. Research Society of Japan"},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G. Laman","year":"1970","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures, J. Engrg. Math., 4, 1970, pp. 331\u2013340.","journal-title":"J. Engrg. Math."},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V. and Vazirani, V.V.: Matching is as easy as matrix inversion, Combinatorica, vol. 7, 1987, pp. 105\u2013114.","journal-title":"Combinatorica"},{"issue":"No.4","key":"20_CR8","first-page":"305","volume":"29","author":"M. Nakamura","year":"1986","unstructured":"Nakamura, M.: On the Representation of the Rigid Sub-systems of a Plane Link System, J. Op. Res. Soc. of Japan, vol. 29, No. 4, 1986, pp. 305\u2013318.","journal-title":"J. Op. Res. Soc. of Japan"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0024-3795(91)90070-D","volume":"144","author":"H. Narayanan","year":"1991","unstructured":"Narayanan, H.: The Principal Lattice of Partitions of a Submodular function, Linear Algebra and its Applications, 144, 1991, pp. 179\u2013216.","journal-title":"Linear Algebra and its Applications"},{"key":"20_CR10","unstructured":"Narayanan, H., Roy, S. and Patkar, S.: Min k-cut and the Principal Partition of a graph, in Proc. of the Second National Seminar on Theoretical Computer Science, India, 1992."},{"key":"20_CR11","unstructured":"Narayanan, H., Saran, H. and Vazirani, V.V.: Fast parallel algorithms for Matroid Union, Arborescences and edge-disjoint spanning trees, in Proc. 3 rd ann. ACM-SIAM Symp. on Discrete Algorithms, 1992."},{"key":"20_CR12","unstructured":"Patkar, S. and Narayanan, H.: Principal Lattice of Partitions of the Rank Function of a Graph, Technical Report VLSI-89-3, I.I.T. Bombay, 1989."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Patkar, S. and Narayanan, H.: Fast algorithm for the Principal Partition of a graph, in Proc. 11 th ann. symp. on Foundations of Software Technology and Theoretical Computer Science (FST & TCS-11), LNCS-560, 1991, pp. 288\u2013306.","DOI":"10.1007\/3-540-54967-6_76"},{"key":"20_CR14","volume-title":"Ph.D. thesis","author":"S. Patkar","year":"1992","unstructured":"Patkar, S.:Investigations into the structure of graphs through the Principal Lattice of Partitions approach, Ph.D. thesis, Dept. of Computer Sci. and Engg., IIT Bombay, INDIA, 1992."},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Saran, H. and Vazirani, V.V.: Finding a k-Cut within Twice the Optimal, Proc. 32 nd annual Symp. on the Foundations of Computer Science, 1991.","DOI":"10.1109\/SFCS.1991.185443"},{"key":"20_CR16","volume-title":"Matroid Theory","author":"D. J. A. Welsh","year":"1976","unstructured":"Welsh, D. J. A.: Matroid Theory, Academic Press, New York, 1976."}],"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-56287-7_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:03:14Z","timestamp":1605646994000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56287-7_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562870","9783540475071"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-56287-7_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}