An Exact Algorithm for the Minimum Dominating Set Problem
Authors: Hua Jiang, Zhifei Zheng
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive empirical results show that the new lower bound is efficient in reduction of the search space and the new algorithm is effective for the standard instances and real-world instances. Extensive experiments were conducted to evaluate the performance of the new algorithm and the lower bound. The results show that the lower bound can reduce the search space efficiently and the proposed Bn B algorithm is effective for the standard instances for MDS and even can solve MDS in real-world large graphs. |
| Researcher Affiliation | Academia | Hua Jiang , Zhifei Zheng Engineering Research Center of Cyberspace & School of Software, Yunnan University, China huajiang@ynu.edu.cn, zzfreya@mail.ynu.edu.cn |
| Pseudocode | Yes | Algorithm 1 EMOS(G), an exact algorithm for MDS; Algorithm 2 Bn BSearch(G, D, U, D ); Algorithm 3 Reduce Branches(G, D, U, D ), algorithm to identify a branching set B |
| Open Source Code | Yes | Published at https://github.com/huajiang-ynu/ijcai23-mds/ |
| Open Datasets | Yes | Experiments were conducted on two standard datasets UDG and T1 and a dataset of real-world graphs, which are widely used to evaluate algorithms for MDS [Jovanovic et al., 2010; Hedar and Ismail, 2010; Potluri and Singh, 2013; Wang et al., 2018; Fan et al., 2019; Cai et al., 2020]. We select from Network Repository2. http://networkrepository.com/networks.php |
| Dataset Splits | No | The paper mentions testing on datasets and setting cutoff times and random seeds, but it does not specify explicit train, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | Yes | Experiments were performed on AMD EPYC CPUs 7702 @2.0GHz under Linux with 128GB of memory. |
| Software Dependencies | Yes | We implemented the new algorithm EMOS1 in C and complied it with GNU gcc -O3. The source code of the three algorithms was kindly provided by their authors and was compiled using GNU g++ -O3. |
| Experiment Setup | Yes | We tested EMOS on the three datasets with a cutoff time of 5 hours for each instance. For those instances that EMOS can solve within the cutoff time, we ran the heuristic algorithms on them 10 times using random seeds 1 to 10 and a cutoff time of 1800s for each run. According to our experiments, k is fixed to 16 in Algorithm 3. |