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

Heal, Maher; Dashtipour, Kia; Gogate, Mandar

Abstract

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.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 2022 International Conference on Computational Science and Computational Intelligence (CSCI)
• Start Date: Dec 14, 2022
• End Date: Dec 16, 2022
• Online Publication Date: Aug 25, 2023
• Publication Date: 2022
• Deposit Date: Apr 19, 2024
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 516-520
• Book Title: Proceedings, 2022 International Conference on Computational Science and Computational Intelligence, CSCI 2022
• ISBN: 9798350320282
• DOI: https://doi.org/10.1109/csci58124.2022.00097
• Keywords: binary programming, multi-variable polynomial programming, maximal independent sets, maximum independent set, polynomial time algorithms
• Public URL: http://researchrepository.napier.ac.uk/Output/3597116