Sliding Window Temporal Graph Coloring
Authors: George B. Mertzios, Hendrik Molter, Viktor Zamaraev7667-7674
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH). |
| Researcher Affiliation | Academia | George B. Mertzios Department of Computer Science Durham University Durham, UK george.mertzios@durham.ac.uk Hendrik Molter Algorithmics and Computational Complexity, Fakult at IV, TU Berlin Berlin, Germany h.molter@tu-berlin.de Viktor Zamaraev Department of Computer Science Durham University Durham, UK viktor.zamaraev@durham.ac.uk |
| Pseudocode | No | The paper describes algorithms in prose (e.g., Theorem 4.5), but it does not present them in structured pseudocode blocks or algorithms explicitly labeled as such. |
| Open Source Code | No | The paper does not contain any statement about making source code publicly available or provide links to a code repository. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity and algorithm design; it does not involve empirical studies with datasets, training, or public dataset availability. |
| Dataset Splits | No | This is a theoretical paper focused on computational complexity and algorithm design; it does not involve empirical studies with data splits (train/validation/test). |
| Hardware Specification | No | This is a theoretical paper that does not report on empirical experiments; therefore, it does not provide hardware specifications for running experiments. |
| Software Dependencies | No | This is a theoretical paper that does not report on empirical experiments; therefore, it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that does not report on empirical experiments; therefore, it does not describe experimental setup details like hyperparameters or system-level settings. |