Finding Diverse Trees, Paths, and More
Authors: Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi3778-3786
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | 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. |