{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:44Z","timestamp":1759639004491},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,10,25]],"date-time":"2008-10-25T00:00:00Z","timestamp":1224892800000},"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,1]]},"DOI":"10.1007\/s00453-008-9239-2","type":"journal-article","created":{"date-parts":[[2008,10,24]],"date-time":"2008-10-24T14:54:46Z","timestamp":1224860086000},"page":"17-34","source":"Crossref","is-referenced-by-count":8,"title":["Minimum Degree Orderings"],"prefix":"10.1007","volume":"56","author":[{"given":"Hiroshi","family":"Nagamochi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,25]]},"reference":[{"key":"9239_CR1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1145\/800182.810393","volume-title":"Proceedings of the 1974 annual conference (ACM74)","author":"G. Alia","year":"1974","unstructured":"Alia, G., Maestrini, P.: An approach to optimal partitioning of hypergraphs. In: Proceedings of the 1974 annual conference (ACM74), pp. 133\u2013139. Assoc. Comput. Mach. Press, New York (1974)"},{"key":"9239_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(99)00071-X","volume":"70","author":"S.R. Arikati","year":"1999","unstructured":"Arikati, S.R., Mehlhorn, K.: A correctness certificate for the Stoer-Wagner min-cut algorithm. Inf. Process. Lett. 70, 251\u2013254 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9239_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jagm.2000.1093","volume":"37","author":"A.A. Bencz\u00far","year":"2000","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Augmenting undirected edge connectivity in $\\tilde{O}(n^{2})$ time. J. Algorithms 37, 2\u201336 (2000)","journal-title":"J. Algorithms"},{"key":"9239_CR4","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0378-8733(90)90014-Z","volume":"12","author":"S.P. Borgatti","year":"1990","unstructured":"Borgatti, S.P., Everett, M.G., Shirey, P.R.: Ls sets, lambda sets and other cohesive subsets. Soc. Netw. 12, 337\u2013357 (1990)","journal-title":"Soc. Netw."},{"key":"9239_CR5","unstructured":"Chekuri, C.S., Goldberg, A.V., Karger, D.R., Levine, M.S., Stein, C.: Experimental study of minimum cut algorithms. In: Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997) pp.\u00a0324\u2013333"},{"key":"9239_CR6","first-page":"290","volume-title":"Studies in Discrete Optimization","author":"E.A. Dinits","year":"1976","unstructured":"Dinits, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimal weighted cuts in a graph. In: Fridman, A.A. (ed.) Studies in Discrete Optimization, pp. 290\u2013306. Nauka, Moscow (1976). (in Russian)"},{"key":"9239_CR7","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9239_CR8","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. SIAM J. Appl. Math. 9, 551\u2013570 (1961)","journal-title":"SIAM J. Appl. Math."},{"key":"9239_CR9","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48, 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"9239_CR10","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47, 46\u201376 (2000)","journal-title":"J. ACM"},{"key":"9239_CR11","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problems. J. ACM 43, 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"9239_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"E.L. Lawler","year":"1973","unstructured":"Lawler, E.L.: Cutsets and partitions of hypergraphs. Networks 3, 275\u2013285 (1973)","journal-title":"Networks"},{"key":"9239_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1109\/TCT.1969.1082924","volume":"16","author":"F. Luccio","year":"1969","unstructured":"Luccio, F., Sami, M.: On the decomposition of networks in minimally interconnected subnetworks. IEEE Trans. Circuit Theory 16, 184\u2013188 (1969)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"9239_CR14","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1137\/0122040","volume":"22","author":"D.W. Matula","year":"1972","unstructured":"Matula, D.W.: k-Components, clusters, and slicings in graphs. SIAM J. Appl. Math. 22, 459\u2013480 (1972)","journal-title":"SIAM J. Appl. Math."},{"key":"9239_CR15","first-page":"417","volume":"30","author":"D.W. Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J.\u00a0ACM 30, 417\u2013427 (1983)","journal-title":"J.\u00a0ACM"},{"key":"9239_CR16","first-page":"199","volume":"47","author":"H. Nagamochi","year":"2004","unstructured":"Nagamochi, H.: Graph algorithms for network connectivity problems. J. Oper. Res. Soc. J. 47, 199\u2013223 (2004)","journal-title":"J. Oper. Res. Soc. J."},{"key":"9239_CR17","first-page":"428","volume":"E90-D","author":"H. Nagamochi","year":"2007","unstructured":"Nagamochi, H.: Computing a minimum cut in a graph with dynamic edges incident to a designated vertex. IEICE Trans. Fundam. E90-D, 428\u2013431 (2007)","journal-title":"IEICE Trans. Fundam."},{"key":"9239_CR18","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"9239_CR19","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity of multigraphs and capacitated graphs. SIAM J. Discrete Math. 5, 54\u201366 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9239_CR20","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0020-0190(98)00114-8","volume":"67","author":"H. Nagamochi","year":"1998","unstructured":"Nagamochi, H., Ibaraki, T.: A note on minimizing submodular functions. Inf. Process. Lett. 67, 239\u2013244 (1998)","journal-title":"Inf. Process. Lett."},{"key":"9239_CR21","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.ipl.2006.11.011","volume":"102","author":"H. Nagamochi","year":"2007","unstructured":"Nagamochi, H., Kamidoi, Y.: Minimum cost subpartitions in graphs. Inf. Process. Lett. 102, 79\u201384 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9239_CR22","doi-asserted-by":"crossref","first-page":"1139","DOI":"10.1137\/S0097539792234226","volume":"26","author":"D. Naor","year":"1997","unstructured":"Naor, D., Gusfield, D., Martel, C.: A fast algorithm for optimally increasing the edge connectivity. SIAM J. Comput. 26, 1139\u20131165 (1997)","journal-title":"SIAM J. Comput."},{"key":"9239_CR23","first-page":"3","volume":"82","author":"M. Queyranne","year":"1998","unstructured":"Queyranne, M.: Minimizing symmetric submodular functions. Math. Program. 82, 3\u201312 (1998)","journal-title":"Math. Program."},{"key":"9239_CR24","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1007\/11682462_70","volume":"3887","author":"M. Sakashita","year":"2006","unstructured":"Sakashita, M., Makino, K., Fujishige, S.: Minimum cost source location problems with flow requirements. Lect. Notes Comput. Sci. 3887, 769\u2013780 (2006)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9239_CR25","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular function in strongly polynomial time. J. Comb. Theory (B) 80, 346\u2013355 (2000)","journal-title":"J. Comb. Theory (B)"},{"key":"9239_CR26","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0378-8733(83)90020-5","volume":"5","author":"S.B. Seidman","year":"1983","unstructured":"Seidman, S.B.: Internal cohesion of ls sets in graphs. Soc. Netw. 5, 97\u2013107 (1983)","journal-title":"Soc. Netw."},{"key":"9239_CR27","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M. Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min cut algorithm. J. ACM 44, 585\u2013591 (1997)","journal-title":"J. ACM"},{"key":"9239_CR28","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T. Watanabe","year":"1987","unstructured":"Watanabe, T., Nakamura, A.: Edge-connectivity augmentation problems. J. Comput. Syst. Sci. 35, 96\u2013144 (1987)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9239-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9239-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9239-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9239-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,25]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9239"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9239-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,25]]}}}