Scholarlink

<p>This paper presents a soft computing based method to solve the problem of the maximum independent set, which is one of the major problems in distributed computing. The maximum independent set is an NP-hard problem for all types of graphs. The proposed method features a robust approach that produces a result in polynomial time. We propose a hybrid Gray wolf optimizer and genetic algorithm. This combination helps to find better solutions more efficiently. The main objective of the hybrid approach is to balance exploration in which trying different possibilities is handled by the grey wolf optimizer, which focuses on and improves the best possibilities which are handled by the genetic algorithm. Our proposed GWO_GA algorithm achieves a polynomial time complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n^2)\)</EquationSource> </InlineEquation> for dense graphs and <i>O</i>(<i>n</i>) for sparse graphs, ensuring better scalability and efficiency for large-scale Maximum Independent Set problems. GWO_GA gives polynomial result in 24 DIMACS benchmark dataset and 10 Miscellaneous benchmark dataset. In traditional approaches, they take exponential time complexity or struggle with convergence and scalability (Tarjan and Trojanowski. in SIAM J Comput 6(3):537–546, 1977; Robson. in J Algor 7(3):425–440, 1986; Bourgeois et al. (A bottom-up method and fast algorithms for max independent set, 2010); Silva-Muñoz et al. in Appl Soft Comput 144:110474, 2023), but this hybrid algorithm achieves near optimal solution in polynomial time, efficiently scaling to large graph instances.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maximum Independent Sets Using Hybrid Approach of Grey Wolf Optimizer and Genetic Algorithm

  • 期刊论文

  • 发表日期：

    2025年12月2日

查看全文
  • Ritika Verma,
  • Dharmendra Prasad Mahato

摘要

This paper presents a soft computing based method to solve the problem of the maximum independent set, which is one of the major problems in distributed computing. The maximum independent set is an NP-hard problem for all types of graphs. The proposed method features a robust approach that produces a result in polynomial time. We propose a hybrid Gray wolf optimizer and genetic algorithm. This combination helps to find better solutions more efficiently. The main objective of the hybrid approach is to balance exploration in which trying different possibilities is handled by the grey wolf optimizer, which focuses on and improves the best possibilities which are handled by the genetic algorithm. Our proposed GWO_GA algorithm achieves a polynomial time complexity of \(O(n^2)\) for dense graphs and O(n) for sparse graphs, ensuring better scalability and efficiency for large-scale Maximum Independent Set problems. GWO_GA gives polynomial result in 24 DIMACS benchmark dataset and 10 Miscellaneous benchmark dataset. In traditional approaches, they take exponential time complexity or struggle with convergence and scalability (Tarjan and Trojanowski. in SIAM J Comput 6(3):537–546, 1977; Robson. in J Algor 7(3):425–440, 1986; Bourgeois et al. (A bottom-up method and fast algorithms for max independent set, 2010); Silva-Muñoz et al. in Appl Soft Comput 144:110474, 2023), but this hybrid algorithm achieves near optimal solution in polynomial time, efficiently scaling to large graph instances.