Scholarlink

<p>The maximum edge weighted clique (MEWC) problem is a generalization of the maximum clique problem and has widely been applied to model lots of problems arising in real-world applications. Due to its NP-hardness, previous work can hardly solve instances with large sizes. To further improve the performance of MEWC algorithms on massive instances, we develop a novel exact algorithm by combining the branch-and-bound framework and two main ideas, which is called BnBM. First, applying the two-level independent set partition a tighter upper bound is proposed to prune branches and improve the efficiency. Second, to remove as many redundant vertices as possible, a fast reduction mechanism is applied during the search. Extensive experiments are conducted to evaluate the performance of our algorithm. On the 139 real-world large instances, within the same cutoff time (7200 seconds), our proposed BnBM solves 24 instances more than the state-of-the-art exact solvers. Meanwhile, considering the efficiency BnBM achieves a speedup on 75 out of 139 instances. However, for 8 instances BnBM is slower than state-of-the-art solvers, and we conduct a deep analysis of the branching process and find the main reasons are the data structure and the structure of the original graph.</p>

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

An exact algorithm with a new upper bound and reductions for maximum edge weighted clique in massive sparse graphs

  • 期刊论文

  • 发表日期：

    2026年1月21日

查看全文
  • Shuli Hu,
  • Jiaqi Li,
  • Wen Wen,
  • Yupeng Zhou,
  • Ruizhi Li,
  • Minghao Yin

摘要

The maximum edge weighted clique (MEWC) problem is a generalization of the maximum clique problem and has widely been applied to model lots of problems arising in real-world applications. Due to its NP-hardness, previous work can hardly solve instances with large sizes. To further improve the performance of MEWC algorithms on massive instances, we develop a novel exact algorithm by combining the branch-and-bound framework and two main ideas, which is called BnBM. First, applying the two-level independent set partition a tighter upper bound is proposed to prune branches and improve the efficiency. Second, to remove as many redundant vertices as possible, a fast reduction mechanism is applied during the search. Extensive experiments are conducted to evaluate the performance of our algorithm. On the 139 real-world large instances, within the same cutoff time (7200 seconds), our proposed BnBM solves 24 instances more than the state-of-the-art exact solvers. Meanwhile, considering the efficiency BnBM achieves a speedup on 75 out of 139 instances. However, for 8 instances BnBM is slower than state-of-the-art solvers, and we conduct a deep analysis of the branching process and find the main reasons are the data structure and the structure of the original graph.