{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:55Z","timestamp":1781345695263,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,3,15]],"date-time":"2008-03-15T00:00:00Z","timestamp":1205539200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00453-008-9177-z","type":"journal-article","created":{"date-parts":[[2008,3,14]],"date-time":"2008-03-14T14:46:53Z","timestamp":1205506013000},"page":"394-412","source":"Crossref","is-referenced-by-count":10,"title":["A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph"],"prefix":"10.1007","volume":"56","author":[{"given":"Vladimir","family":"Kolmogorov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,3,15]]},"reference":[{"key":"9177_CR1","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: Optimal attack and reinforcement of a network. J. ACM 32, 549\u2013561 (1985)","journal-title":"J. ACM"},{"key":"9177_CR2","doi-asserted-by":"crossref","unstructured":"Narayanan, H.: The principal lattice of partitions of a submodular function. In: Linear Algebra and Its Applications, vol.\u00a0144, pp.\u00a0179\u2013216 (1991)","DOI":"10.1016\/0024-3795(91)90070-D"},{"key":"9177_CR3","doi-asserted-by":"crossref","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 the spanning tree polytope. Oper. Res. Let. 12, 201\u2013203 (1992)","journal-title":"Oper. Res. Let."},{"key":"9177_CR4","doi-asserted-by":"crossref","first-page":"6973","DOI":"10.1088\/0305-4470\/35\/33\/301","volume":"35","author":"J.-C.A. d\u2019Auriac","year":"2002","unstructured":"d\u2019Auriac, J.-C.A., Igloi, F., Preissmann, M., Sebo, A.: Optimal cooperation and submodularity for computing Potts\u2019 partition functions with a large number of states. J. Phys. A: Math. Gen. 35, 6973\u20136983 (2002)","journal-title":"J. Phys. A: Math. Gen."},{"key":"9177_CR5","doi-asserted-by":"crossref","first-page":"186","DOI":"10.15807\/jorsj.26.186","volume":"26","author":"H. Imai","year":"1983","unstructured":"Imai, H.: Network flow algorithms for lower truncated transversal polymatroids. J. Oper. Res. Soc. Jpn. 26, 186\u2013210 (1983)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"1","key":"9177_CR6","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1023\/A:1021994406231","volume":"7","author":"S. Patkar","year":"2003","unstructured":"Patkar, S., Narayanan, H.: Fast on-line\/off-line algorithms for optimal reinforcement of a network and its connections with principal partition. J. Comb. Optim. 7(1), 45\u201368 (2003)","journal-title":"J. Comb. Optim."},{"key":"9177_CR7","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M., Tarjan, R.E.: A fast parametric network flow algorithm. SIAM J. Comput. 18, 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"key":"9177_CR8","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. Lipton","year":"1979","unstructured":"Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"9177_CR9","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Electrical Networks","author":"H. Narayanan","year":"1997","unstructured":"Narayanan, H.: Submodular Functions and Electrical Networks. Annals of Discrete Mathematics, vol.\u00a054. North Holland, Amsterdam (1997)"},{"key":"9177_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-56279-6_56","volume-title":"Proc. of the 3rd Ann. Int. Symp. on Algorithms and Computation (ISAAC)","author":"S. Patkar","year":"1992","unstructured":"Patkar, S., Narayanan, H.: Principal lattice of partitions of submodular functions on graphs: fast algorithms for principal partition and generic rigidity. In: Proc. of the 3rd Ann. Int. Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol.\u00a0650, pp. 41\u201350. Springer, Berlin (1992)"},{"key":"9177_CR11","doi-asserted-by":"crossref","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. Comput. 20, 639\u2013654 (1991)","journal-title":"SIAM J. Comput."},{"key":"9177_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(94)90013-2","volume":"49","author":"E. Cheng","year":"1994","unstructured":"Cheng, E., Cunningham, W.H.: A faster algorithm for computing the strength of a network. Inf. Process. Lett. 49, 209\u2013212 (1994)","journal-title":"Inf. Process. Lett."},{"key":"9177_CR13","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1006\/jagm.1997.0904","volume":"26","author":"H.N. Gabow","year":"1998","unstructured":"Gabow, H.N.: Algorithms for graphic polymatroids and parametric s-sets. J. Algorithms 26, 48\u201386 (1998)","journal-title":"J. Algorithms"},{"key":"9177_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"1991","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics. North Holland, Amsterdam (1991)"},{"key":"9177_CR15","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Proc. Calgary Int. Conf. on Combinatorial Structures and Applications, pp.\u00a069\u201387 (1970)"},{"issue":"3","key":"9177_CR16","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1109\/TSE.1978.231502","volume":"4","author":"H.S. Stone","year":"1978","unstructured":"Stone, H.S.: Critical load factors in two-processor distributed systems. IEEE Trans. Softw. Eng. 4(3), 254\u2013258 (1978)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"4","key":"9177_CR17","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"M.J. Eisner","year":"1976","unstructured":"Eisner, M.J., Severence, D.G.: Mathematical techniques for efficient record segmentation in large shared databases. J. ACM 23(4), 619\u2013635 (1976)","journal-title":"J. ACM"},{"issue":"5","key":"9177_CR18","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"S.T. McCormick","year":"1999","unstructured":"McCormick, S.T.: Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. 47(5), 744\u2013756 (1999)","journal-title":"Oper. Res."},{"issue":"4","key":"9177_CR19","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"issue":"3","key":"9177_CR20","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9177_CR21","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"9177_CR22","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1287\/moor.25.2.243.12223","volume":"25","author":"M. Ba\u00efou","year":"2000","unstructured":"Ba\u00efou, M., Barahona, F., Mahjoub, A.R.: Separation of partition inequalities. Math. Oper. Res. 25(2), 243\u2013254 (2000)","journal-title":"Math. Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9177-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9177-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9177-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:01Z","timestamp":1559137501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9177-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,15]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9177"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9177-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,15]]}}}