The maximum independent union of cliques problem: complexity and exact approaches Academic Article

abstract

• 2018, Springer Science+Business Media, LLC, part of Springer Nature. Given a simple graph, the maximum independent union of cliques problem is to find a maximum-cardinality subset of vertices such that each connected component of the corresponding induced subgraph is a complete graph. This recently introduced problem allows both cliques and independent sets as feasible solutions and is of significant theoretical and applied interest. This paper establishes the complexity of the problem on several classes of graphs (planar, claw-free, and bipartite graphs), and develops an integer programming formulation and an exact combinatorial branch-and-bound algorithm for solving it. Results of numerical experiments with numerous benchmark instances are also reported.

authors

• Butenko, Sergiy

published proceedings

• JOURNAL OF GLOBAL OPTIMIZATION

author list (cited authors)

• Ertem, Z., Lykhovyd, E., Wang, Y., & Butenko, S.

citation count

• 6

complete list of authors

• Ertem, Zeynep||Lykhovyd, Eugene||Wang, Yiming||Butenko, Sergiy

publication date

• March 2020

publisher

• Springer Nature  Publisher

published in

• Journal of Global Optimization  Journal

keywords

• Clique
• Cluster Vertex Deletion
• Independent Set
• Independent Union Of Cliques
• Network Clustering

Digital Object Identifier (DOI)

• 10.1007/s10898-018-0694-2

start page

• 545

end page

• 562

volume

• 76

issue

• 3

URL

• http://dx.doi.org/10.1007/s10898-018-0694-2