{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:11:39Z","timestamp":1750306299655,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2016,1,29]],"date-time":"2016-01-29T00:00:00Z","timestamp":1454025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) as part of the Priority Program \u201cAlgorithm Engineering\u201d","award":["LU770\/4-1 and LU770\/4-2"],"award-info":[{"award-number":["LU770\/4-1 and LU770\/4-2"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2016,11,4]]},"abstract":"<jats:p>The cut packing problem in an undirected graph is to find a largest cardinality collection of pairwise edge-disjoint cuts. We provide the first experimental study of this NP-hard problem that is interesting from a pure theorist\u2019s viewpoint as well as from the standpoint of scientific applications (e.g., in bioinformatics and network reliability). So far it could not be solved exactly. We propose a branch-price-and-cut algorithm to optimally solve instances from various graph classes, random and from the literature, with up to several hundred vertices. In particular, we investigate how complexity results match computational experience and how combinatorial properties help improve the algorithm\u2019s performance.<\/jats:p>","DOI":"10.1145\/2851492","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T20:37:54Z","timestamp":1454359074000},"page":"1-16","source":"Crossref","is-referenced-by-count":0,"title":["A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs"],"prefix":"10.1145","volume":"21","author":[{"given":"Martin","family":"Bergner","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Marco E.","family":"L\u00dcbbecke","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Jonas T.","family":"Witt","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2016,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-008-0001-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/588"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_4"},{"key":"e_1_2_1_4_1","unstructured":"R. Bornd\u00f6rfer and Z. Kormos. 1997. An algorithm for maximum cliques. Unpublished working paper Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin.  R. Bornd\u00f6rfer and Z. Kormos. 1997. An algorithm for maximum cliques. Unpublished working paper Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00052-X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v44:1"},{"key":"e_1_2_1_7_1","unstructured":"C. J. Colbourn. 1987. The Combinatorics of Network Reliability. Oxford University Press New York NY.   C. J. Colbourn. 1987. The Combinatorics of Network Reliability. Oxford University Press New York NY."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90193-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.40.2.342"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"J. Desrosiers and M. E. L\u00fcbbecke. 2011. Branch-price-and-cut algorithms. In Encyclopedia of Operations Research and Management Science J. J. Cochran (Ed.). John Wiley & Sons Chichester. DOI:http:\/\/dx.doi.org\/10.1002\/9780470400531.eorms0118  J. Desrosiers and M. E. L\u00fcbbecke. 2011. Branch-price-and-cut algorithms. In Encyclopedia of Operations Research and Management Science J. J. Cochran (Ed.). John Wiley & Sons Chichester. DOI:http:\/\/dx.doi.org\/10.1002\/9780470400531.eorms0118","DOI":"10.1002\/9780470400531.eorms0118"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Vol. 3. Springer Heidelberg.  R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Vol. 3. Springer Heidelberg.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_13_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Vol. 3. Springer.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Vol. 3. Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_21"},{"volume-title":"Proc. 8th ALENEX. 86--94","author":"Gramm J.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","unstructured":"A. Gutfraind L. A. Meyers and I. Safro. 2012. Multiscale Network Generation. (2012). arXiv:1207.4266.  A. Gutfraind L. A. Meyers and I. Safro. 2012. Multiscale Network Generation. (2012). arXiv:1207.4266."},{"volume-title":"Proceedings of the 7th Python in Science Conference (SciPy2008)","author":"Hagberg A. A.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523693"},{"key":"e_1_2_1_20_1","first-page":"96","article-title":"A Simple Hypergraph Min Cut Algorithm","author":"Klimmek R.","year":"1996","journal-title":"Technical Report B"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359346"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"e_1_2_1_23_1","unstructured":"S. Pettie and V. Ramachandran. 2006. Randgraph graph generator. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml.  S. Pettie and V. Ramachandran. 2006. Randgraph graph generator. Retrieved from http:\/\/www.dis.uniroma1.it\/challenge9\/download.shtml."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9264-3"},{"key":"e_1_2_1_25_1","unstructured":"G. Rinaldi. 1998. Rudy a graph generator. Retrieved from http:\/\/www-user.tu-chemnitz.de\/&sim;helmberg\/sdp_software.html.  G. Rinaldi. 1998. Rudy a graph generator. Retrieved from http:\/\/www-user.tu-chemnitz.de\/&sim;helmberg\/sdp_software.html."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1976.63"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_1_30_1","unstructured":"M. Trick. 1993. Coloring instances. Retreived from http:\/\/mat.gsia.cmu.edu\/COLOR\/instances.html.  M. Trick. 1993. Coloring instances. Retreived from http:\/\/mat.gsia.cmu.edu\/COLOR\/instances.html."},{"volume-title":"BHOSLIB: Benchmarks with hidden optimum solutions for graph problems.","year":"2010","author":"Xu K.","key":"e_1_2_1_31_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2851492","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2851492","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:15Z","timestamp":1750221555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2851492"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,29]]},"references-count":30,"alternative-id":["10.1145\/2851492"],"URL":"https:\/\/doi.org\/10.1145\/2851492","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2016,1,29]]}}}