Solving maximum clique in sparse graphs: an O(nm+n2d/4) algorithm for d
-degenerate graphs

Solving maximum clique in sparse graphs: an O(nm+n2d/4) algorithm for d -degenerate graphs

0.00 Avg rating0 Votes
Article ID: iaor2014862
Volume: 8
Issue: 5
Start Page Number: 1611
End Page Number: 1617
Publication Date: Jun 2014
Journal: Optimization Letters
Authors: , , ,
Keywords: maximum clique
Abstract:

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy d equ1 . The algorithm runs in O n m + n T d equ2 time, where T d equ3 is the time to solve the maximum clique problem in an arbitrary graph on d equ4 vertices. The best bound as of now is T d = O ( 2 d / 4 ) equ5 by Robson. This shows that the maximum clique problem is solvable in O ( n m ) equ6 time in graphs for which d 4 log 2 m + O ( 1 ) equ7 . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi‐Marsili power‐law random graphs, it runs in 2 O ( n ) equ8 time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.

Reviews

Required fields are marked *. Your email address will not be published.