Branch-and-Cut Algorithms for Colorful Components Problems

References

• Adamaszek A, Popa A (2014) Algorithmic and hardness results for the colorful components problems. Pardo A, Viola A, eds. LATIN 2014: Theoretical Informatics, Lecture Notes in Computer Science, vol. 8392 (Springer, Berlin, Heidelberg), 683–694.Google Scholar
• Adamaszek A, Blin G, Popa A (2015) Approximation and hardness results for the maximum edges in transitive closure problem. Jan K, Miller M, Froncek D, eds. Combin. Algorithms. IWOCA 2014, Lecture Notes in Computer Science, vol. 8986 (Springer, Cham, Switzerland), 13–23.Google Scholar
• Ambrosio G, Cerulli R, Serra D, Sorgente C, Vaccaro U (2025) Exact and heuristic solution approaches for the cluster deletion problem on general graphs. Networks 85(4):351–367.Crossref, Google Scholar
• Archetti C, Cerulli M, Sorgente C (2025) Branch-and-cut algorithms for colorful components problems. https://doi.org/10.1287/ijoc.2024.0927.cd, https://github.com/INFORMSJoC/2024.0927.Google Scholar
• Avidor A, Langberg M (2007) The multi-multiway cut problem. Theoret. Comput. Sci. 377(1):35–42.Crossref, Google Scholar
• Benzer S (1959) On the topology of the genetic fine structure. Proc. Natl. Acad. Sci. USA 45(11):1607–1620.Crossref, Google Scholar
• Bruckner S, Hüffner F, Komusiewicz C, Niedermeier R (2013) Evaluation of ILP-based approaches for partitioning into colorful components. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds. Experimental Algorithms, SEA 2013, Lecture Notes in Computer Science, vol. 7933 (Springer, Berlin, Heidelberg), 176–187.Google Scholar
• Bruckner S, Hüffner F, Komusiewicz C, Niedermeier R, Thiel S, Uhlmann J (2012) Partitioning into colorful components by minimum edge deletions. Kärkkäinen J, Stoye J, eds. Combinatorial Pattern Matching, CPM 2012, Lecture Notes in Computer Science, vol. 7354 (Springer, Berlin, Heidelberg), 56–69.Google Scholar
• Cerulli M, Serra D, Sorgente C, Archetti C, Ljubić I (2023) Mathematical programming formulations for the collapsed k-core problem. Eur. J. Oper. Res. 311(1):56–72.Crossref, Google Scholar
• Chandrasekaran K, Karp R, Moreno-Centeno E, Vempala S (2011) Algorithms for implicit hitting set problems. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 614–629.Google Scholar
• De Melo G, Weikum G (2010) Untangling the cross-lingual link structure of Wikipedia. Hajič J, Carberry S, Clark S, Nivre J, eds. Proc. 48th Annual Meeting Assoc. Comput. Linguistics (Association for Computational Linguistics, Kerrville, TX), 844–853.Google Scholar
• Dondi R, Sikora F (2018) Parameterized complexity and approximation issues for the colorful components problems. Theoret. Comput. Sci. 739:1–12.Crossref, Google Scholar
• Furini F, Ljubic I, Martin S, San Segundo P (2019) The maximum clique interdiction problem. Eur. J. Oper. Res. 277(1):112–127.Crossref, Google Scholar
• Grötschel M, Wakabayashi Y (1989) A cutting plane algorithm for a clustering problem. Math. Programming 45:59–96.Crossref, Google Scholar
• He G, Liu J, Zhao C (2000) Approximation algorithms for some graph partitioning problems. J. Graph Algorithms Appl. 4(2):1–11.Crossref, Google Scholar
• Hu TC (1963) Multi-commodity network flows. Oper. Res. 11(3):344–360.Link, Google Scholar
• Liu X, Xie H, Yan Z, Liang X (2023) A survey on blockchain sharding. ISA Trans. 141:30–43.Crossref, Google Scholar
• Matula DW (1987) Determining edge connectivity in 0(nm). 28th Annual Sympos. Foundations Comput. Sci. (Sfcs 1987) (IEEE, Piscataway, NJ), 249–251.Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10:147–175.Crossref, Google Scholar
• Misra N (2018) On the parameterized complexity of colorful components and related problems. Iliopoulos C, Leong H, Sung WK, eds. Combinatorial Algorithms, IWOCA 2018, Lecture Notes in Computer Science, vol. 10979 (Springer, Cham, Switzerland), 237–249.Google Scholar
• Moreno-Centeno E, Karp RM (2013) The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Oper. Res. 61(2):453–468.Link, Google Scholar
• Natanzon A, Shamir R, Sharan R (2001) Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1):109–128.Crossref, Google Scholar
• Shamir R, Sharan R, Tsur D (2004) Cluster graph modification problems. Discrete Appl. Math. 144(1):173–182.Crossref, Google Scholar
• Sritharan R (2016) Graph modification problem for some classes of graphs. J. Discrete Algorithms 38–41:32–37.Crossref, Google Scholar
• Thompson JD, Koehl P, Ripp R, Poch O (2005) BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark. Proteins: Structure Function Bioinformatics 61(1):127–136.Crossref, Google Scholar
• Wei N, Walteros JL, Pajouh FM (2021) Integer programming formulations for minimum spanning tree interdiction. INFORMS J. Comput. 33(4):1461–1480.Abstract, Google Scholar
• Yannakakis M (1978) Node-and edge-deletion NP-complete problems. STOC’78: Proc. 10th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 253–264.Google Scholar
• Yannakakis M (1981) Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1):77–79.Crossref, Google Scholar
• Zenklusen R (2010) Matching interdiction. Discrete Appl. Math. 158(15):1676–1690.Crossref, Google Scholar
• Zheng C, Swenson K, Lyons E, Sankoff D (2011) OMG! Orthologs in multiple genomes – Competing graph-theoretical formulations. Przytycka TM, Sagot MF, eds. Algorithms in Bioinformatics, WABI 2011, Lecture Notes in Computer Science, vol. 6833 (Springer, Berlin, Heidelberg), 364–375.Google Scholar