A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm
In this study, a method has been developed for solving the maximum independent set problem, which is one of the significant problems in graph theory. The maximum independent set problem is NP-hard for all types of graphs. The proposed method features a robust and greedy approach that produces result...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-03-01
|
| Series: | Engineering Science and Technology, an International Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2215098625000503 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850229264797925376 |
|---|---|
| author | Furkan Öztemiz |
| author_facet | Furkan Öztemiz |
| author_sort | Furkan Öztemiz |
| collection | DOAJ |
| description | In this study, a method has been developed for solving the maximum independent set problem, which is one of the significant problems in graph theory. The maximum independent set problem is NP-hard for all types of graphs. The proposed method features a robust and greedy approach that produces results in polynomial time for all graph types. The proposed method is named the Differential Malatya Independent Set Algorithm (DMISA). The presented method also provides solutions to the minimum vertex cover and maximum clique problems, which are directly related to the independent set. The DMISA algorithm consists of two sub-algorithms. The first algorithm is the Differential Malatya Centrality Algorithm (DMCA), a centrality algorithm that calculates centrality values, providing prioritization in the selection of independent members. The second algorithm uses the DMCA value to select the independent set and vertex cover members in the graphs. In this study, the DMISA analytical proof has been applied to graphs with known solutions that can be solved in polynomial time. To emphasize the success of the algorithm, test operations have been conducted on various types of graphs. The conducted tests included 40 lattices, 40 bipartite, 24 multipartite, 32 social, and random graphs. The analysis results showed that DMISA produced optimal results in lattice, bipartite, and complete multipartite graphs, while it produced generally non-optimal results for randomly generated and social graphs. Additionally, DMISA is compared with MIS methods in popular graph libraries and 7 different MIS methods. In summary, DMISA produces a larger solution than standard greedy algorithms in experiments. |
| format | Article |
| id | doaj-art-491135e1bd7540f88c691237d190c09e |
| institution | OA Journals |
| issn | 2215-0986 |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Engineering Science and Technology, an International Journal |
| spelling | doaj-art-491135e1bd7540f88c691237d190c09e2025-08-20T02:04:18ZengElsevierEngineering Science and Technology, an International Journal2215-09862025-03-016310199510.1016/j.jestch.2025.101995A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithmFurkan Öztemiz0Department of Software Engineering Inonu University Malatya TurkeyIn this study, a method has been developed for solving the maximum independent set problem, which is one of the significant problems in graph theory. The maximum independent set problem is NP-hard for all types of graphs. The proposed method features a robust and greedy approach that produces results in polynomial time for all graph types. The proposed method is named the Differential Malatya Independent Set Algorithm (DMISA). The presented method also provides solutions to the minimum vertex cover and maximum clique problems, which are directly related to the independent set. The DMISA algorithm consists of two sub-algorithms. The first algorithm is the Differential Malatya Centrality Algorithm (DMCA), a centrality algorithm that calculates centrality values, providing prioritization in the selection of independent members. The second algorithm uses the DMCA value to select the independent set and vertex cover members in the graphs. In this study, the DMISA analytical proof has been applied to graphs with known solutions that can be solved in polynomial time. To emphasize the success of the algorithm, test operations have been conducted on various types of graphs. The conducted tests included 40 lattices, 40 bipartite, 24 multipartite, 32 social, and random graphs. The analysis results showed that DMISA produced optimal results in lattice, bipartite, and complete multipartite graphs, while it produced generally non-optimal results for randomly generated and social graphs. Additionally, DMISA is compared with MIS methods in popular graph libraries and 7 different MIS methods. In summary, DMISA produces a larger solution than standard greedy algorithms in experiments.http://www.sciencedirect.com/science/article/pii/S2215098625000503Maximum independent setMinimum vertex coverMaximum cliqueCentrality algorithm |
| spellingShingle | Furkan Öztemiz A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm Engineering Science and Technology, an International Journal Maximum independent set Minimum vertex cover Maximum clique Centrality algorithm |
| title | A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm |
| title_full | A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm |
| title_fullStr | A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm |
| title_full_unstemmed | A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm |
| title_short | A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm |
| title_sort | greedy approach to solve maximum independent set problem differential malatya independent set algorithm |
| topic | Maximum independent set Minimum vertex cover Maximum clique Centrality algorithm |
| url | http://www.sciencedirect.com/science/article/pii/S2215098625000503 |
| work_keys_str_mv | AT furkanoztemiz agreedyapproachtosolvemaximumindependentsetproblemdifferentialmalatyaindependentsetalgorithm AT furkanoztemiz greedyapproachtosolvemaximumindependentsetproblemdifferentialmalatyaindependentsetalgorithm |