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 [1].
Finding Diverse Trees, Paths, and More
Authors: Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi3778-3786
AAAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we further investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph G and an integer r, the problem of computing r spanning trees of G maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size. |
| Researcher Affiliation | Academia | Tesshu Hanaka1, Yasuaki Kobayashi2, Kazuhiro Kurita3, Yota Otachi4 1Chuo University, Tokyo, Japan 2Kyoto University, Kyoto, Japan 3National Institute of Informatics, Tokyo, Japan 4Nagoya University, Nagoya, Japan |
| Pseudocode | Yes | Algorithm 1 Given a vertex-colored graph G = (V, E) with c : V [k] and an integer k, find a colorful k-path in G |
| Open Source Code | No | The paper mentions that 'some contents are deferred to the full version (Hanaka et al. 2020)', which is an arXiv link, but it does not state that source code for the methodology is openly available or provide a direct link to a code repository within the provided text. |
| Open Datasets | No | The paper is theoretical and does not mention using any datasets for training or evaluation, nor does it provide access information for any public datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits, thus no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not discuss experimental hardware specifications such as GPU or CPU models. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe experimental setups, hyperparameters, or training configurations. |