华中科技大学学报（自然科学版）2024，Vol.52Issue(11)：43-49,7.DOI:10.13245/j.hust.241106
基于渐增式奖励上界的最大k-plex问题求解
Incremental reward based on upper bound for solving maximum k-plex problem
摘要
Abstract
Aiming at the problem that the pruning rate was affected by branching strategy for exact maximum k-plex algorithm,a vertex strategy was proposed based on reinforcement learning and upper bound reward.This strategy gained an upper bound by partitioning the candidate set,and rewarded the branching vertex with the variation of upper bound to evaluate the impact of branching actions on subgraphs.An incremental reward computation was implemented to reduce the learning costs.By incorporating the method of dividing the candidate set into branch set and non-branch set,the new strategy prioritized selecting the vertex with the highest accumulated reward from the branch set.To evaluate the performance of the proposed strategy,it was tested on 211 graphs from 10thDIMACS and Real-word benchmarks.Experimental results show that compared to the state-of-the-art KpLeX and Maplex algorithms,the proposed IRkplex algorithm reduces the average running time by 2.00%～23.71%,indicating that the vertex strategy can effectively improve the pruning rate.关键词
最大k-plex问题/非确定多项式复杂度的难度问题/强化学习/奖励函数/分支策略Key words
maximum k-plex problem/non-deterministic polynomial hard problem/reinforcement learning/reward function/branching strategy分类
信息技术与安全科学引用本文复制引用
刘燕丽,迟思义,刘浪,何琨..基于渐增式奖励上界的最大k-plex问题求解[J].华中科技大学学报（自然科学版）,2024,52(11):43-49,7.基金项目
国家自然科学基金资助项目(U22B2017) （U22B2017）
湖北省教育厅资助项目(Q20211111). （Q20211111）
