Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871272 | Discrete Applied Mathematics | 2018 | 12 Pages |
Abstract
To carry out a clique search in a given graph in a parallel fashion, one divides the problem into a very large number of smaller instances. To sort out as many resulted smaller problems as possible, one can rely on upper estimates of the clique sizes. Legal coloring of the nodes of the graphs is a commonly used tool to establish upper bound of the clique size. We will point out that coloring of the nodes can also be used to divide the clique search problem into smaller ones. We will introduce a non-conventional coloring of the edges of the given graph. We will gather theoretical and computational evidence that the proposed edge coloring provides better estimates for the clique size than the node coloring and can be used to divide the original problem into subproblems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sándor Szabó, Bogdan Zavalnij,