Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Exactly Solving Minimum Dominating Set and Its Generalization
Authors: Ziliang Xiong, Mingyu Xiao
IJCAI 2024 | Venue PDF | 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 EMAIL, EMAIL |
| 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. |