{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:46Z","timestamp":1751282866691},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562795"},{"type":"electronic","value":"9783540475019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56279-6_56","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:59:14Z","timestamp":1330253954000},"page":"41-50","source":"Crossref","is-referenced-by-count":5,"title":["Principal lattice of partitions of submodular functions on graphs: Fast algorithms for principal partition and generic rigidity"],"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,9]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Gabow, H.N. and Westermann, H.H.: Forests, Frames and Games: Algorithms for Matroid sums and Applications, in Proc. 20th STOC, 1988, pp. 407\u2013421.","DOI":"10.1145\/62212.62252"},{"key":"5_CR2","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"},{"issue":"no.1","key":"5_CR3","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1080\/00207728108963728","volume":"12","author":"M. Iri","year":"1981","unstructured":"Iri, M. and Fujishige, S.: Use of Matroid Theory in Operations Research, Circuits and Systems Theory, Int. J. Systems Sci.,vol. 12, no. 1, 1981, pp. 27\u201354.","journal-title":"Int. J. Systems Sci."},{"issue":"No.4","key":"5_CR4","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":"5_CR5","volume-title":"Ph.D. thesis","author":"H. Narayanan","year":"1974","unstructured":"Narayanan, H.: Theory of Matroids and Network Analysis, Ph.D. thesis, Department of Electrical Engineering, IIT Bombay, INDIA, 1974."},{"key":"5_CR6","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":"5_CR7","volume-title":"Technical Report VLSI-89-3","author":"S. Patkar","year":"1989","unstructured":"Patkar, S. and Narayanan, H.: Principal Lattice of Partitions of the Rank Function of a Graph, Technical Report VLSI-89-3, IIT Bombay, INDIA, 1989."},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Patkar, S. and Narayanan, H.: Fast algorithm for the Principal Partition of a graph, in Proc. 11th 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":"5_CR9","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":"5_CR10","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D. and Tarjan, R.E.: A data structure for dynamic trees, J. Comp. and System Sci., vol. 26, 1983, pp. 362\u2013391.","journal-title":"J. Comp. and System Sci."},{"key":"5_CR11","first-page":"376","volume":"44","author":"K. Sugihara","year":"1980","unstructured":"Sugihara, K.: On Redundant Bracing in Plane Skeletal Structures, Bulletin of the Electrotechnical Laboratory, vol. 44, 1980, pp. 376\u2013386.","journal-title":"Bulletin of the Electrotechnical Laboratory"},{"key":"5_CR12","first-page":"83","volume":"J59A","author":"N. Tomizawa","year":"1976","unstructured":"Tomizawa, N.: Strongly Irreducible Matroids and Principal Partition of a Matroid into Strongly Irreducible Minors (in Japanese), Transactions of the Institute of Electronics and Communication Engineers of Japan, vol. J59A, 1976, pp. 83\u201391.","journal-title":"Transactions of the Institute of Electronics and Communication Engineers of Japan"},{"key":"5_CR13","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","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56279-6_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:02:57Z","timestamp":1605646977000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56279-6_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562795","9783540475019"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-56279-6_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}