Formulations and Algorithms to Find Maximal and Maximum Independent Sets of Graphs

Research Output

We propose four algorithms to find maximal and maximum independent sets of graphs. Two of the algorithms are non-polynomial in time, mainly binary programming and non-convex multi-variable polynomial programming algorithms. Two other algorithms run in polynomial time seek to find a maximum independent set. The algorithms depend on our earlier work in [10]. The main advantage and the difference of the new algorithms is that we do not need to enumerate the maximal cliques of the graphs. We applied the algorithms to some graphs from DIMACS and other graphs and their performance was seen to be adequate.

Date:

25 August 2023
Publication Status:

Published
Publisher

IEEE
DOI:

10.1109/csci58124.2022.00097
Funders:

Edinburgh Napier Funded

http://researchrepository.napier.ac.uk/output/3597116 <p>Heal, M., Dashtipour, K., & Gogate, M. (2023). Formulations and Algorithms to Find Maximal and Maximum Independent Sets of Graphs. In <i>Proceedings, 2022 International Conference on Computational Science and Computational Intelligence, CSCI 2022</i>. https://doi.org/10.1109/csci58124.2022.00097</p>

Citation

Heal, M., Dashtipour, K., & Gogate, M. (2023). Formulations and Algorithms to Find Maximal and Maximum Independent Sets of Graphs. In Proceedings, 2022 International Conference on Computational Science and Computational Intelligence, CSCI 2022. https://doi.org/10.1109/csci58124.2022.00097