Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks Academic Article

abstract

• This paper explores techniques for solving the maximum clique and vertex coloring problems on very large-scale real-life networks. Because of the size of such networks and the intractability of the considered problems, previously developed exact algorithms may not be directly applicable. The proposed approaches aim to reduce the network instances to a size that is tractable for existing solvers, while preserving optimality. Two clique relaxation structures are exploited for this purpose. In addition to the known k-core structure, a newly introduced clique relaxation, k-community, is used to further reduce the instance size. Experimental results on real-life graphs (collaboration networks, P2P networks, social networks, etc.) show the proposed procedures to be effective by finding, for the first time, exact solutions for instances with over 18 million vertices.

authors

• Butenko, Sergiy

published proceedings

• INFORMS JOURNAL ON COMPUTING

altmetric score

• 1.5

author list (cited authors)

• Verma, A., Buchanan, A., & Butenko, S.

citation count

• 39

complete list of authors

• Verma, Anurag||Buchanan, Austin||Butenko, Sergiy

publication date

• January 2015

publisher

• Institute for Operations Research and the Management Sciences (INFORMS)  Publisher

published in

• INFORMS Journal on Computing  Journal

keywords

• Clique Relaxation
• Exact Algorithm
• K-community
• K-core
• Maximum Clique
• Scale Reduction
• Vertex Coloring
• Very-large-scale Networks

Digital Object Identifier (DOI)

• 10.1287/ijoc.2014.0618

start page

• 164

end page

• 177

volume

• 27

issue

• 1

URL

• http://dx.doi.org/10.1287/ijoc.2014.0618