A Refined Upper Bound and Inprocessing for the Maximum K-plex Problem
Authors: Hua Jiang, Fusheng Xu, Zhifei Zheng, Bowen Wang, Wei Zhou
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experiments show that both the refined upper bound and the inprocessing strategy are very efficient in the reduction of search space. The new algorithm outperforms the state-of-the-art algorithms on the tested benchmarks significantly.6 Experimental Results We empirically evaluated the new algorithm Dise MKP and its two essential components: the refined upper bound and the inprocessing strategy. |
| Researcher Affiliation | Academia | Hua Jiang , Fusheng Xu , Zhifei Zheng , Bowen Wang , Wei Zhou Engineering Research Center of Cyberspace & School of Software, Yunnan University, China huajiang@ynu.edu.cn,{xfs, zzfreya, morningnews}@mail.ynu.edu.cn, zwei@ynu.edu.cn |
| Pseudocode | Yes | Algorithm 1 Dise PUB(S, C, k), a partition algorithm based on distribution efficiency. (and Algorithm 2, 3, 4, 5) |
| Open Source Code | Yes | Dise MKP4 Published at https://github.com/huajiang-ynu/ijcai23-kpx |
| Open Datasets | Yes | DIMACS graphs5: The dataset contains 80 graphs with the number of vertices up to 4000 and densities ranging from 0.03 to 0.99. The dataset has been widely used to evaluate algorithms for MCP and MKP. 5http://archive.dimacs.rutgers.edu/pub/challenge/graph/ |
| Dataset Splits | No | The paper mentions using 675 graphs from three different datasets for evaluation but does not specify training, validation, or test dataset splits (e.g., percentages, sample counts, or cross-validation setup). |
| Hardware Specification | Yes | Experiments were performed on AMD EPYC CPUs 7702 @2.0GHz under Linux with 128GB of memory. |
| Software Dependencies | No | The paper states that algorithms were 'implemented in C++ and compiled using GNU g++ -O3' but does not provide specific version numbers for the C++ standard or the GNU g++ compiler, nor for any other key software libraries or dependencies. |
| Experiment Setup | Yes | We use four different k values: 2, 4, 6 and 8 to evaluate the algorithms. ... Algorithms were tested over the 675 instances with a cutoff time of 1800s for each instance. |