Book Chapter
Details
Citation
Heal M & Li J (2020) Finding the Maximal Independent Sets of a Graph Including the Maximum Using a Multivariable Continuous Polynomial Objective Optimization Formulation. In: Arai K, Kapoor S & Bhatia R (eds.) Intelligent Computing. SAI 2020. Advances in Intelligent Systems and Computing, 1228. Cham, Switzerland: Springer International Publishing, pp. 122-136. https://doi.org/10.1007/978-3-030-52249-0_9
Abstract
We propose a multivariable continuous polynomial optimization formulation to find arbitrary maximal independent sets of any size for any graph. A local optima of the optimization problem yields a maximal independent set, while the global optima yields a maximum independent set. The solution is two phases. The first phase is listing all the maximal cliques of the graph and the second phase is solving the optimization problem. We believe that our algorithm is efficient for sparse graphs, for which there exist fast algorithms to list their maximal cliques. Our algorithm was tested on some of the DIMACS maximum clique benchmarks and produced results efficiently. In some cases our algorithm outperforms other algorithms, such as cliquer.
Keywords
Independent set; Continuous optimization; MATLAB; Maximal cliques; Sparse graphs
Status | Published |
---|---|
Title of series | Advances in Intelligent Systems and Computing |
Number in series | 1228 |
Publication date | 31/12/2020 |
Publication date online | 04/07/2020 |
URL | http://hdl.handle.net/1893/31424 |
Publisher | Springer International Publishing |
Place of publication | Cham, Switzerland |
ISSN of series | 2194-5357 |
ISBN | 9783030522483 |
eISBN | 9783030522490 |
People (1)
PhD Researcher, Computing Science and Mathematics - Division