Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

D. Agarwal, J.-C.S. Araujo, C. Caillouet, F. Cazals, D. Coudert, S. Pérennes, Connectivity inference in mass spectrometry based structure determination, in: European Symposium on Algorithms, in: Lecture Notes in Computer Science, 2013, pp. 289–300. Agarwal, 2015, Unveiling contacts within macromolecular assemblies by solving minimum weight connectivity inference (MWC) problems, Mol. Cell. Proteomics, 14, 2274, 10.1074/mcp.M114.047779 D. Angluin, J. Aspnes, L. Reyzin, Inferring social networks from outbreaks, in: International Conference on Algorithmic Learning Theory, in: Lecture Notes in Computer Science, 2010, pp. 104–118. É. Bonnet, D.-E. Fălămaş, R. Watrigant, Constraint generation algorithm for the minimum connectivity inference problem, in: International Symposium on Experimental Algorithms, SEA 2019: Analysis of Experimental Algorithms, 2019, pp. 167–183. Chen, 2016, Algorithms based on divide and conquer for topic-based publish/subscribe overlay design, IEEE/ACM Trans. Netw., 24, 422, 10.1109/TNET.2014.2369346 Chen, 2015, Polynomial-time data reduction for the subset interconnection design problem, SIAM J. Discrete Math., 29, 1, 10.1137/140955057 G. Chockler, R. Melamed, Y. Tock, R. Vitenberg, Constructing scalable overlays for pub-sub with many topics, in: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007, pp. 109–118. Christofides, 1976 Chwatal, 2011, Solving the minimum label spanning tree problem by mathematical programming techniques, Adv. Oper. Res., 2011 Conforti, 2010, Extended formulations in combinatorial optimization, 4OR: Q. J. Oper. Res., 8, 1, 10.1007/s10288-010-0122-z Dar, 2019, A computational study of reduction techniques for the minimum connectivity inference problem, 135 Dar, 2019, An improved flow-based formulation and reduction principles for the minimum connectivity inference problem, Optimization, 68, 1963, 10.1080/02331934.2018.1465944 Du, 1986, An optimization problem on graphs, Discrete Appl. Math., 14, 101, 10.1016/0166-218X(86)90010-7 Du, 1995, On complexity of subset interconnection designs, J. Global Optim., 6, 193, 10.1007/BF01096768 Du, 1988, Matroids and subset interconnection design, SIAM J. Discrete Math., 1, 416, 10.1137/0401042 N. Fan, M. Golari, Integer programming formulations for minimum spanning forests and connected components in sparse graphs, in: Proceedings of the International Conference on Combinatorial Optimization and Applications, 2014, pp. 613–622. Fan, 2008, Algorithms and implementation for interconnection graph problem, 201 Hosoda, 2012, On the approximability and hardness of minimum topic connected overlay and its special instances, Theoret. Comput. Sci., 429, 144, 10.1016/j.tcs.2011.12.033 Kruskal, 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 48, 10.1090/S0002-9939-1956-0078686-7 Magnanti, 1995, Optimal trees, 503, 10.1016/S0927-0507(05)80126-4 Martin, 1991, Using separation algorithms to generate mixed integer model reformulations, Oper. Res. Lett., 3, 119, 10.1016/0167-6377(91)90028-N Pop, 2004, New models of the generalized minimum spanning tree problem, J. Math. Model. Algorithms, 3, 153, 10.1023/B:JMMA.0000036579.83218.8d Prisner, 1992, Two algorithms for the subset interconnection design problem, Networks, 22, 385, 10.1002/net.3230220406 K.J. Supowit, D.A. Plaisted, E.M. Reingold, Heuristics for weighted perfect matching, in: Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC ’80, 1980, pp. 398–419. Wang, 2014, Clustering with Prim’s sequential representation of minimum spanning tree, Appl. Math. Comput., 247, 521, 10.1016/j.amc.2014.09.026 Zhong, 2011, Minimum spanning tree based split-and-merge: A hierarchical clustering method, Inform. Sci., 181, 3397, 10.1016/j.ins.2011.04.013 Zhong, 2010, A graph-theoretical clustering method based on two rounds of minimum spanning trees, Pattern Recognit., 43, 752, 10.1016/j.patcog.2009.07.010