{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:55Z","timestamp":1725664255717},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583387"},{"type":"electronic","value":"9783540486633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58338-6_99","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:51:06Z","timestamp":1330271466000},"page":"525-535","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach"],"prefix":"10.1007","author":[{"given":"H.","family":"Narayanan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subir","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sachin","family":"Patkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"45_CR1","volume-title":"Flows in Networks","author":"L. R. Ford","year":"1962","unstructured":"Ford, L. R. & Fulkerson, D. R.: Flows in Networks, Princeton University Press, Princeton, 1962."},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O. and Hochbaum, D.S.: Polynomial algorithm for the k-cut problem, Proc. 29 th annual Symp. on the Foundations of Computer Science, 1988,pp. 444\u2013451.","DOI":"10.1109\/SFCS.1988.21960"},{"key":"45_CR3","first-page":"186","volume":"26","author":"H. Imai","year":"1983","unstructured":"Imai, H.: Network flow algorithms for lower truncated transversal polymatroids, Jl. of the Op. Research Society of Japan, vol. 26, 1983, pp. 186\u2013210.","journal-title":"Jl. of the Op. Research Society of Japan"},{"issue":"no.1","key":"45_CR4","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."},{"key":"45_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4400-4","volume-title":"The Design and Analysis of Algorithms","author":"D.C. Kozen","year":"1992","unstructured":"Kozen, D.C.: The Design and Analysis of Algorithms, Springer-Verlag, New York, 1992."},{"key":"45_CR6","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"Lawler, E. L.: Combinatorial Optimization: Networks and Matroids, Holt, Reinhart and Winston, New York, 1976."},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Lovasz, L.: Submodular Functions and Convexity, Proceedings of XI International Symposium on Mathematical Programming, Bonn, 1982.","DOI":"10.1007\/978-3-642-68874-4_10"},{"issue":"no.6","key":"45_CR8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V.M. Malhotra","year":"1978","unstructured":"Malhotra, V.M., Kumar, M.P., & Maheshwari, S.N.: An O (\u00a6V\u00a63) Algorithm for Finding Maximum Flows in Networks, Information Processing Letters, 7, no.6, 1978, pp. 277\u2013278.","journal-title":"Information Processing Letters"},{"key":"45_CR9","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, I.I.T. Bombay, 1974."},{"key":"45_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1002\/cta.4490180305","volume":"18","author":"H. Narayanan","year":"1990","unstructured":"Narayanan, H.: On the minimum hybrid rank of a graph relative to a partition of its edges and its application to electrical network analysis, Intl. Journal of Circuit Theory and Applications, Vol. 18, 1990, pp. 269\u2013288.","journal-title":"Intl. Journal of Circuit Theory and Applications"},{"key":"45_CR11","doi-asserted-by":"crossref","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":"45_CR12","volume-title":"Min k-Cut and the Principal Partition of a Graph","author":"H. Narayanan","year":"1992","unstructured":"Narayanan, H., Roy, Subir, & Patkar, Sachin: Min k-Cut and the Principal Partition of a Graph, Proceedings of the Second National Seminar on Theoretical Computer Science, Indian Statistical Institute, Calcutta, June 17\u201319, 1992."},{"key":"45_CR13","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/3-540-54967-6_76","volume":"560","author":"S. Patkar","year":"1991","unstructured":"Patkar, S. and Narayanan, H.: Fast algorithm for the Principal Partition of a graph, Proc. 11th Annual Symposium on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science \u2014 560, 1991, pp. 288\u2013306.","journal-title":"Lecture Notes in Computer Science"},{"key":"45_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-56279-6_56","volume":"650","author":"S. Patkar","year":"1992","unstructured":"Patkar, S. and Narayanan, H.: Principal Lattice of Partitions of submodular functions on graphs: Fast algorithms for Principal Partition and Generic Rigidity, in Proc. of the 3 rd ann. Int. Symp. on Algorithms and Computation, (ISAAC), Lecture Notes in Computer Science-650, Japan, 1992, pp. 41\u201350.","journal-title":"Lecture Notes in Computer Science"},{"key":"45_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"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1994"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58338-6_99.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:19:54Z","timestamp":1605647994000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58338-6_99"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583387","9783540486633"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-58338-6_99","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}