{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:10:29Z","timestamp":1737436229861,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_7","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"94-105","source":"Crossref","is-referenced-by-count":2,"title":["Fast On-Line\/Off-Line Algorithms for Optimal Reinforcement of a Network and Its Connections with Principal Partition"],"prefix":"10.1007","author":[{"given":"Sachin B.","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":[[2000,11,24]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0167-6377(92)90045-5","volume":"12","author":"F. Barahona","year":"1992","unstructured":"Barahona, F.: Separating from the dominant of spanning tree polytope,Oper. Res. Letters, vol. 12, 1992, pp.201\u2013203.","journal-title":"Oper. Res. Letters"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(94)90013-2","volume":"49","author":"E. Cheng","year":"1994","unstructured":"Cheng, E. and Cunningham, W.: A faster algorithm for computing thestrength of a network, Information Processing Letters, vol. 49, 1994, pp.209\u2013212.","journal-title":"Information Processing Letters"},{"issue":"3","key":"7_CR3","first-page":"549","volume":"32","author":"W. Cunningham","year":"1985","unstructured":"Cunningham, W.: Optimal attack and reinforcement of a network, JACM,vol. 32, no. 3, 1985, pp.549\u2013561.","journal-title":"Optimal attack and reinforcement of a network"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1287\/mnsc.13.7.492","volume":"13","author":"W. Dinkelbach","year":"1967","unstructured":"Dinkelbach, W.: On nonlinear fractional programming, Management Sci.,vol. 13, 1967, pp.492\u2013498.","journal-title":"Management Sci"},{"key":"7_CR5","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra, Proc.Calgary Intl. conference on Combinatorial Structures, 1970, pp.69\u201387."},{"key":"7_CR6","unstructured":"Fujishige, S.:Submodular Functions and Optimization, Annals of DiscreteMathematics, North Holland, 1991."},{"key":"7_CR7","first-page":"48","volume":"26","author":"H.N. Gabow","year":"1998","unstructured":"Gabow, H.N.: Algorithms for graphic polymatroids and parametric s-sets J.Algorithms, vol. 26, 1998, pp.48\u201386.","journal-title":"Algorithms for graphic polymatroids and parametric s-sets J.Algorithms"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M. and Tarjan, R.E.: A fast parametric network flow algorithm, SIAM J. of Computing, vol. 18, 1989, pp.30\u201355.","journal-title":"SIAM J. of Computing"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1137\/0220040","volume":"20","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Computing the strength of a graph, SIAM J. of Computing,vol. 20, 1991, pp.639\u2013654.","journal-title":"SIAM J. of Computing"},{"key":"7_CR10","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":"1","key":"7_CR11","doi-asserted-by":"publisher","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, circuitsand systems theory, Int. J. Systems Sci.,vol. 12, no. 1, 1981, pp. 27\u201354.","journal-title":"Int. J. Systems Sci."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Itai, A. and Rodeh, M.: The multi-tree approach to reliability in distributednetworks, in Proc. 25th ann. symp. FOCS, 1984, pp. 137\u2013147.","DOI":"10.1109\/SFCS.1984.715910"},{"key":"7_CR13","unstructured":"Narayanan, H.:Theory of matroids and network analysis, Ph.D. thesis, Departmentof Electrical Engineering, I.I.T. Bombay, 1974."},{"key":"7_CR14","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":"7_CR15","first-page":"306","volume":"21","author":"H. Narayanan","year":"1996","unstructured":"Narayanan, H., Roy, S. and Patkar, S.B.: Approximation Algorithms formin-k-overlap Problems, using the Principal Lattice of Partitions Approach,J. of Algorithms, vol. 21, 1996, pp. 306\u2013330.","journal-title":"using the Principal Lattice of Partitions Approach,J. of Algorithms"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Narayanan, H.: Submodular Functions and Electrical Networks, Annals ofDiscrete Mathematics-54, North Holland, 1997.","DOI":"10.1016\/S0167-5060(08)70678-2"},{"key":"7_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-56279-6_56","volume-title":"Principal lattice of partitions of submodularfunctions on graphs: fast algorithms for principal partition and genericrigidity","author":"S. Patkar","year":"1992","unstructured":"Patkar, S. and Narayanan, H.: Principal lattice of partitions of submodularfunctions on graphs: fast algorithms for principal partition and genericrigidity, in Proc. of the 3rd ann. Int. Symp. on Algorithms and Computation,(ISAAC), LNCS-650, Japan, 1992, pp. 41\u201350."},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Patkar, S. and Narayanan, H.: Fast On-line\/Off-line Algorithms for OptimalReinforcement of a Network and its Connections with Principal Partition,Technical Report, Industrial Mathematics Group, Department of Mathematics,IIT Bombay, available from authors via e-mail, 2000.","DOI":"10.1007\/3-540-44450-5_7"},{"key":"7_CR19","first-page":"83","volume":"J59A","author":"N. Tomizawa","year":"1976","unstructured":"Tomizawa, N.: Strongly irreducible matroids and principal partition of amatroid into strongly irreducible minors (in Japanese), Transactions of theInstitute of Electronics and Communication Engineers of Japan, vol. J59A,1976, pp. 83\u201391.","journal-title":"Transactions of theInstitute of Electronics and Communication Engineers of Japan"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T11:30:13Z","timestamp":1737372613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}