{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:12Z","timestamp":1740109332268,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T00:00:00Z","timestamp":1694476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["AF-1814613","AF-1907937"],"award-info":[{"award-number":["AF-1814613","AF-1907937"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s10107-023-02013-8","type":"journal-article","created":{"date-parts":[[2023,9,12]],"date-time":"2023-09-12T13:02:42Z","timestamp":1694523762000},"page":"329-367","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k"],"prefix":"10.1007","volume":"207","author":[{"given":"Calvin","family":"Beideman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3421-7238","authenticated-orcid":false,"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weihang","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,12]]},"reference":[{"issue":"1\u20132","key":"2013_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0944-8","volume":"154","author":"H Aissi","year":"2015","unstructured":"Aissi, H., Mahjoub, A., McCormick, T., Queyranne, M.: Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math. Program. 154(1\u20132), 3\u201328 (2015)","journal-title":"Math. Program."},{"key":"2013_CR2","unstructured":"Beideman, C., Chandrasekaran, K., Wang, W.: Counting and enumerating optimum cut sets for hypergraph $$k$$-partitioning problems for fixed $$k$$. In: Proceedings of the 49th International Colloquium on Automata, Languages and Programming, ICALP, pp.\u00a016:1\u201316:22 (2022)"},{"key":"2013_CR3","doi-asserted-by":"crossref","unstructured":"Chandrasekaran, K., Chekuri, C.: Min\u2013max partitioning of hypergraphs and symmetric submodular functions. In: Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a01026\u20131038 (2021)","DOI":"10.1137\/1.9781611976465.64"},{"key":"2013_CR4","doi-asserted-by":"publisher","first-page":"3380","DOI":"10.1287\/moor.2021.1250","volume":"47","author":"K Chandrasekaran","year":"2022","unstructured":"Chandrasekaran, K., Chekuri, C.: Hypergraph $$k$$-cut for fixed $$k$$ in deterministic polynomial time. Math. Oper. Res. 47, 3380\u20133399 (2022)","journal-title":"Math. Oper. Res."},{"key":"2013_CR5","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10107-019-01443-7","volume":"186","author":"K Chandrasekaran","year":"2019","unstructured":"Chandrasekaran, K., Xu, C., Yu, X.: Hypergraph $$k$$-cut in randomized polynomial time. Math. Program. 186, 85\u2013113 (2019)","journal-title":"Math. Program."},{"issue":"2","key":"2013_CR6","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1137\/19M1299359","volume":"34","author":"C Chekuri","year":"2020","unstructured":"Chekuri, C., Quanrud, K., Xu, C.: LP relaxation and tree packing for minimum $$k$$-cut. SIAM J. Discrete Math. 34(2), 1334\u20131353 (2020)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"2013_CR7","doi-asserted-by":"publisher","first-page":"2118","DOI":"10.1137\/18M1163865","volume":"47","author":"C Chekuri","year":"2018","unstructured":"Chekuri, C., Xu, C.: Minimum cuts and sparsification in hypergraphs. SIAM J. Comput. 47(6), 2118\u20132156 (2018)","journal-title":"SIAM J. Comput."},{"key":"2013_CR8","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s101070050032","volume":"84","author":"E Cheng","year":"1999","unstructured":"Cheng, E.: Edge-augmentation of hypergraphs. Math. Program. 84, 443\u2013465 (1999)","journal-title":"Math. Program."},{"key":"2013_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02579341","volume":"3","author":"W Cunningham","year":"1980","unstructured":"Cunningham, W.: Decomposition of submodular functions. Combinatorica 3, 53\u201368 (1980)","journal-title":"Combinatorica"},{"key":"2013_CR10","doi-asserted-by":"publisher","first-page":"734","DOI":"10.4153\/CJM-1980-057-7","volume":"32","author":"W Cunningham","year":"1980","unstructured":"Cunningham, W., Edmonds, J.: A combinatorial decomposition theory. Can. J. Math 32, 734\u2013765 (1980)","journal-title":"Can. J. Math"},{"issue":"4","key":"2013_CR11","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"2013_CR12","volume-title":"Studies in Discrete Optimization","author":"EA Dinitz","year":"1976","unstructured":"Dinitz, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of a family of minimum weighted cuts in a graph. In: Fridman, A.A. (ed.) Studies in Discrete Optimization. Nauka Publishers, Moscow (1976)"},{"key":"2013_CR13","doi-asserted-by":"crossref","unstructured":"Fox, K., Panigrahi, D., Zhang, F.: Minimum cut and minimum $$k$$-cut in hypergraphs via branching contractions. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a0881\u2013896 (2019)","DOI":"10.1137\/1.9781611975482.54"},{"key":"2013_CR14","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0166-218X(83)90040-9","volume":"5","author":"S Fujishige","year":"1983","unstructured":"Fujishige, S.: Canonical decompositions of symmetric submodular functions. Discrete Appl. Math. 5, 175\u2013190 (1983)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"2013_CR15","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.disopt.2013.10.002","volume":"10","author":"T Fukunaga","year":"2013","unstructured":"Fukunaga, T.: Computing minimum multiway cuts in hypergraphs. Discrete Optim. 10(4), 371\u2013382 (2013)","journal-title":"Discrete Optim."},{"key":"2013_CR16","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Karger, D., Panigrahi, D.: Random contractions and sampling for hypergraph and hedge connectivity. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a01101\u20131114 (2017)","DOI":"10.1137\/1.9781611974782.71"},{"key":"2013_CR17","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF01192523","volume":"15","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Ramakrishnan, V.S.: Minimizing submodular functions over families of sets. Combinatorica 15, 499\u2013513 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"2013_CR18","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the $$k$$-cut problem for fixed $$k$$. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"key":"2013_CR19","unstructured":"Gupta, A., Harris, D., Lee, E., Li, J.: Optimal Bounds for the $$k$$-cut Problem. Preprint in arXiv arXiv:2005.08301 (2020)"},{"key":"2013_CR20","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: An FPT algorithm beating 2-approximation for $$k$$-cut. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a02821\u20132837 (2018)","DOI":"10.1137\/1.9781611975031.179"},{"key":"2013_CR21","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: Faster exact and approximate algorithms for k-cut. In: Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp.\u00a0113\u2013123 (2018)","DOI":"10.1109\/FOCS.2018.00020"},{"key":"2013_CR22","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: The number of minimum $$k$$-cuts: improving the Karger\u2013Stein bound. Proceedings of the 51st ACM Symposium on Theory of Computing, STOC, pp.\u00a0229\u2013240 (2019)","DOI":"10.1145\/3313276.3316395"},{"key":"2013_CR23","doi-asserted-by":"crossref","unstructured":"Gupta, A., Lee, E., Li, J.: The Karger\u2013Stein algorithm is optimal for $$k$$-cut. In: Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, STOC, pp.\u00a0473\u2013484 (2020)","DOI":"10.1145\/3357713.3384285"},{"key":"2013_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0304-0208(08)72962-1","volume":"95","author":"JW Hamacher","year":"1984","unstructured":"Hamacher, J.W., Picard, J.-C., Queyranne, M.: Ranking the cuts and cut-sets of a network. N. Holl. Math. Stud. 95, 183\u2013200 (1984)","journal-title":"N. Holl. Math. Stud."},{"key":"2013_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(96)00079-8","volume":"59","author":"M Henzinger","year":"1996","unstructured":"Henzinger, M., Williamson, D.: On the number of small cuts in a graph. Inf. Process. Lett. 59, 41\u201344 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"2013_CR26","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1137\/050631616","volume":"36","author":"Y Kamidoi","year":"2007","unstructured":"Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding all minimum $$k$$-way cuts. SIAM J. Comput. 36(5), 1329\u20131341 (2007)","journal-title":"SIAM J. Comput."},{"key":"2013_CR27","unstructured":"Karger, D.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proceedings of the 4th annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.\u00a021\u201330 (1993)"},{"issue":"1","key":"2013_CR28","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D Karger","year":"2000","unstructured":"Karger, D.: Minimum cuts in near-linear time. J. ACM 47(1), 46\u201376 (2000)","journal-title":"J. ACM"},{"issue":"4","key":"2013_CR29","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D Karger","year":"1996","unstructured":"Karger, D., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"2013_CR30","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1002\/net.3230030306","volume":"3","author":"E Lawler","year":"1973","unstructured":"Lawler, E.: Cutsets and partitions of hypergraphs. Networks 3, 275\u2013285 (1973)","journal-title":"Networks"},{"key":"2013_CR31","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Saurabh, S., Surianarayanan, V.: A parameterized approximation scheme for Min$$k$$-Cut. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp.\u00a0798\u2013809 (2020)","DOI":"10.1109\/FOCS46700.2020.00079"},{"issue":"1","key":"2013_CR32","doi-asserted-by":"publisher","first-page":"10","DOI":"10.3390\/a11010010","volume":"11","author":"P Manurangsi","year":"2018","unstructured":"Manurangsi, P.: Inapproximability of maximum biclique problems, minimum $$k$$-cut and densest at-least-$$k$$-subgraph from the small set expansion hypothesis. Algorithms 11(1), 10 (2018)","journal-title":"Algorithms"},{"key":"2013_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivity. Cambridge University Press, Cambridge (2008)"},{"issue":"3","key":"2013_CR34","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1137\/S0895480194271323","volume":"10","author":"H Nagamochi","year":"1997","unstructured":"Nagamochi, H., Nishimura, K., Ibaraki, T.: Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10(3), 469\u2013481 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"2013_CR35","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00493-019-3900-1","volume":"39","author":"M N\u00e4gele","year":"2019","unstructured":"N\u00e4gele, M., Sudakov, B., Zenklusen, R.: Submodular minimization under congruency constraints. Combinatorica 39, 1351\u20131386 (2019)","journal-title":"Combinatorica"},{"issue":"3","key":"2013_CR36","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/s00453-010-9483-0","volume":"62","author":"K Okumoto","year":"2012","unstructured":"Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems. Algorithmica 62(3), 787\u2013806 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"2013_CR37","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.ejor.2007.01.040","volume":"186","author":"R Ravi","year":"2008","unstructured":"Ravi, R., Sinha, A.: Approximating k-cuts using network strength as a Lagrangean relaxation. Eur. J. Oper. Res. 186(1), 77\u201390 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"2013_CR38","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"2013_CR39","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Minimum $$k$$-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC, pp.\u00a0159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"2013_CR40","doi-asserted-by":"crossref","unstructured":"Vazirani, V., Yannakakis, M.: Suboptimal cuts: their enumeration, weight and number (extended abstract). In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP \u201992, pp.\u00a0366\u2013377 (1992)","DOI":"10.1007\/3-540-55719-9_88"},{"key":"2013_CR41","doi-asserted-by":"crossref","unstructured":"Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In: Proceedings of 19th International Symposium on Algorithms and Computation, ISAAC, pp.\u00a0208\u2013219 (2008)","DOI":"10.1007\/978-3-540-92182-0_21"},{"issue":"14","key":"2013_CR42","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1016\/j.ipl.2010.05.003","volume":"110","author":"M Xiao","year":"2010","unstructured":"Xiao, M.: Finding minimum 3-way cuts in hypergraphs. Inf. Process. Lett. 110(14), 554\u2013558 (2010)","journal-title":"Inf. Process. Lett."},{"key":"2013_CR43","unstructured":"Zhao, L.: Approximation algorithms for partition and design problems in networks, Ph.D. thesis, Graduate School of Informatics, Kyoto University, Japan (2002)"},{"issue":"1","key":"2013_CR44","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-004-0510-2","volume":"102","author":"L Zhao","year":"2005","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Math. Program. 102(1), 167\u2013183 (2005)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02013-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02013-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02013-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T23:35:15Z","timestamp":1730072115000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02013-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,12]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2013"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02013-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,9,12]]},"assertion":[{"value":"4 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}