Compiling Graph Substructures into Sentential Decision Diagrams
Authors: Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, Masaaki Nagata
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We experimentally confirm that the proposed algorithm is faster than other construction methods including bottom-up methods and top-down methods for ZDDs, and the resulting ZSDDs are smaller than ZDDs representing the same graph substructures. |
| Researcher Affiliation | Collaboration | 1NTT Communication Science Laboratories, NTT Corporation 2Graduate School of Information Science and Technology, Hokkaido University |
| Pseudocode | Yes | Algorithm 1: A top-down construction algorithm; Algorithm 2: construct(v, Z); Algorithm 3: Subroutines used for Matchings; Algorithm 4: shannon Child(v, z, t); Algorithm 5: decomp Child(v, z) |
| Open Source Code | No | The paper mentions "1https://github.com/nsnmsak/zsdd" for the bottom-up construction algorithm. This is not for the authors' proposed top-down method. There is no explicit statement or link to the source code for their own proposed top-down compilation algorithm described in the paper. |
| Open Datasets | Yes | We use benchmark graphs used in (Cook and Seymour 2003), which were obtained by applying Delaunay triangulation to the geometric instances in TSPLIB. We also used instances from the Rome Graph dataset 2. |
| Dataset Splits | No | The paper does not provide specific details on how the datasets were split into training, validation, and test sets. It mentions using "benchmark graphs" and "instances" for experiments. |
| Hardware Specification | Yes | All experiments were conducted on a Linux machine with a Xeon E5-2687W 3.10 GHz CPU and 128 GB RAM. |
| Software Dependencies | No | The paper mentions using "graphillion" but does not provide a specific version number. It also references a GitHub link for a bottom-up ZSDD algorithm used for comparison, but this is not a dependency of their proposed method with a version number. |
| Experiment Setup | No | The paper describes the algorithms (Alg. 1-5) and general experimental conditions (benchmarks, comparisons) but does not provide specific experimental setup details such as hyperparameters, model initialization, or training schedules. |