Conceptual clique sampling frameworks to design solution algorithms for the Edge Clique Cover Problem

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 1, January-February 2025


Page(s)		523 - 547
DOI		https://doi.org/10.1051/ro/2024229
Published online		06 February 2025

W.M. Abdullah and S. Hossain, A sparse matrix approach for covering large complex networks by cliques, in International Conference on Computational Science. Springer (2022) 505–517. [Google Scholar]
P.K. Agarwal, N. Alon, B. Aronov and S. Suri, Can visibility graphs be represented compactly? Discrete Comput. Geo. 12 (1994) 347–365. [CrossRef] [Google Scholar]
M. Blanchette, E. Kim and A. Vetta, Clique cover on sparse networks, in 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM (2012) 93–102. [Google Scholar]
G. Boole, Of propositions numerically definite, 1868, in Chapter IV of Studies in Logic and Probability, Waters, London (1952). [Google Scholar]
R. Borndöfer, Aspects of set packing, partitioning, and covering an analysis of example. Ph.D. thesis, Technischen Universit¨at Berlin (1998). [Google Scholar]
M.B. Campêlo, V.A. Campos and R.C. Corrêa, On the asymmetric representatives formulation for the vertex coloring problem. Electron. Notes Discret. Math. 19 (2005) 337–343. [CrossRef] [Google Scholar]
G.J. Chang, The domatic number problem. Discrete Math. 125 (1994) 115–122. [CrossRef] [MathSciNet] [Google Scholar]
A. Conte, R. Grossi and A. Marino, Clique covering of large real-world networks, in Proceedings of the 31st Annual ACM Symposium on Applied Computing (2016) 1134–1139. [Google Scholar]
J. Desrosiers and M.E. Lübbecke, Branch-Price-and-Cut Algorithms. John Wiley & Sons, Ltd. (2011). [Google Scholar]
P. Erdös, A.W. Goodman and L. Pósa, The representation of a graph by set intersections. Can. J. Math. 18 (1966) 106–112. [CrossRef] [Google Scholar]
F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1 (1972) 180–187. [CrossRef] [MathSciNet] [Google Scholar]
J. Gramm, J. Guo, F. Hüffner and R. Niedermeier, Data reduction, exact, and heuristic algorithms for clique cover, in Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics (2006) 86–94. [Google Scholar]
J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, H.-P. Piepho and R. Schmid, Algorithms for compact letter displays: comparison and evaluation. Comput. Stat. Data Anal. 52 (2007) 725–736. [Google Scholar]
J.-L. Guillaume and M. Latapy, Bipartite structure of all complex networks. Inf. Process. Lett. 90 (2004) 215–221. [CrossRef] [Google Scholar]
D. Hermelin, R. Rizzi and S. Vialette, Algorithmic aspects of the intersection and overlap numbers of a graph, in International Symposium on Algorithms and Computation. Springer (2012) 465–474. [Google Scholar]
A. Hevia, B. Kallus, S. McClintic, S. Reisner, D. Strash and J. Wilson, Solving edge clique cover exactly via synergistic data reduction. Preprint: arXiv:2306.17804 (2023). [Google Scholar]
S. Hosseinian, D.B. Fontes, S. Butenko, M.B. Nardelli, M. Fornari and S. Curtarolo, The maximum edge weight clique problem: formulations and solution approaches, in Optimization Methods and Applications. Springer (2017) 217–237. [Google Scholar]
D.S. Johnson and M.R. Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman (1979). [Google Scholar]
L.T. Kou, L.J. Stockmeyer and C.-K. Wong, Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM 21 (1978) 135–139. [CrossRef] [Google Scholar]
M.E. Lübbecke and J. Desrosiers, Selected topics in column generation. Oper. Res. 53 (2005) 1007–1023. [CrossRef] [MathSciNet] [Google Scholar]
A. Lucena, N. Maculan and L. Simonetti, Reformulations and solution algorithms for the maximum leaf spanning tree problem. Comput. Manage. Sci. 7 (2010) 289–311. [CrossRef] [Google Scholar]
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM (JACM) 41 (1994) 960–981. [CrossRef] [Google Scholar]
A. Markham and M. Grosse-Wentrup, Measurement dependence inducing latent causal models, in Conference on Uncertainty in Artificial Intelligence. PMLR (2020) 590–599. [Google Scholar]
T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory. SIAM (1999). [CrossRef] [Google Scholar]
A. Mehrotra and M.A. Trick, A column generation approach for graph coloring. INFORMS J. Comput. 8 (1996) 344–354. [CrossRef] [Google Scholar]
J. Orlin, Contentment in graph theory: covering graphs with cliques, in Indagationes Mathematicae (Proceedings). Vol. 80. Elsevier (1977) 406–424. [Google Scholar]
K. Park, K. Lee and S. Park, An extended formulation approach to the edge-weighted maximal clique problem. Eur. J. Oper. Res. 95 (1996) 671–682. [CrossRef] [Google Scholar]
H.-P. Piepho, An algorithm for a letter-based representation of all-pairwise comparisons. J. Comput. Graph. Stat. 13 (2004) 456–466. [CrossRef] [Google Scholar]
S. Rajagopalan, M. Vachharajani and S. Malik, Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints, in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2000) (2000) 157–164. [Google Scholar]
F.S. Roberts, Applications of edge coverings by cliques. Discrete Appl. Math. 10 (1985) 93–109. [CrossRef] [MathSciNet] [Google Scholar]
C.H.M. Sabóia, Um Algoritmo Branch-and-Price para Instâncias de Grande Porte do Modelo Brasileiro de Planejamento da Expans˜ao da Geraç˜ao Elétrica a Longo Prazo. Ph.D. thesis, Programa de Engenharia de Sistemas e Computaç˜ao – PESC/COPPE, Universidade Federal do Rio de Janeiro (2013). [Google Scholar]
T. Stützle, Local search algorithms for combinatorial problems. Ph.D. thesis, Darmstadt University of Technology (1998). [Google Scholar]
E. Tomita, A. Tanaka and H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363 (2006) 28–42. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.