Exactly Solving Minimum Dominating Set and Its Generalization
Authors: Ziliang Xiong, Mingyu Xiao
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Performance experiments on several standard datasets reveal that our combinatorial algorithm is over 1000 times faster than the previous state-of-the-art exact algorithm presented in IJCAI 2023, and our LP Relaxation algorithm can even enhance the speed of our combinatorial algorithm by over 100 times. Section 4 presents experimental results, comparing our algorithm with the state-of-the-art exact algorithm for MDSP. |
| Researcher Affiliation | Academia | Ziliang Xiong and Mingyu Xiao University of Electronic Science and Technology of China forgottencosecant@outlook.com, myxiao@gmail.com |
| Pseudocode | Yes | Algorithm 1: BIBSearch(I, D ) and Algorithm 2: Reduce(I) |
| Open Source Code | Yes | Our codes and the experimental results are published here4. 4https://anonymous.4open.science/r/IJCAI24-MDS-0570/ |
| Open Datasets | Yes | We conducted experiments on four datasets that are commonly used in the literature [Potluri and Singh, 2011; Jovanovic et al., 2010; Cai et al., 2020; Jiang and Zheng, 2023; Inza et al., 2024] to assess the performance of our algorithms. UDG (Unit Disk Graphs) : This dataset comprises 120 random graphs... T1 : This dataset includes 530 randomly connected graphs... Network Repository : We selected 8 categories of networks... from the well-known Network Repository1[Rossi and Ahmed, 2015]. BD3/BD6 : In [Inza et al., 2024], the authors generated several sets of random graphs... The authors of [Jiang and Zheng, 2023] have made their source code for EMOS, along with the UDG and T1 datasets, publicly available on Github3. |
| Dataset Splits | No | The paper describes the datasets used (UDG, T1, Network Repository, BD3/BD6) and their composition (e.g., number of graphs, types), but it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | Yes | All experiments were conducted on a server equipped with an Intel Xeon Gold 6226R CPU and 512 GB of memory, running Ubuntu Server 20.04 LTS. |
| Software Dependencies | Yes | Our algorithms are implemented in C++ and compiled using gcc version 9.4.0 with the -O3 flag enabled. We use Hi GHS [Huangfu and Hall, 2018] as the LP solver in our algorithms. |
| Experiment Setup | Yes | The time limit for each trial is set to 5 hours, consistent with [Jiang and Zheng, 2023]. Settings Our algorithms are implemented in C++ and compiled using gcc version 9.4.0 with the -O3 flag enabled. |