Faster Dynamic Controllability Checking in Temporal Networks with Integer Bounds
Authors: Nikhil Bhargava, Brian C. Williams
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our work improves the runtime of checking the dynamic controllability of STNUs with integer bounds to O min(mn, m n log N) + km + k2n + kn log n . Our approach pre-processes the STNU using an existing O(n3) dynamic controllability checking algorithm and provides tighter bounds on its runtime. This makes our work easily adaptable to other algorithms that rely on checking variants of dynamic controllability. ... Theorem 3.3. Algorithm 3 runs in worst-case O min(mn, m n log N) + km + k2n + kn log n time for STNUs with integer bounds. |
| Researcher Affiliation | Academia | Nikhil Bhargava1 , Brian C. Williams1 1Massachusetts Institute of Technology {nkb, williams}@mit.edu |
| Pseudocode | Yes | Algorithm 1: Semi-Reducible Negative Cycle Algorithm, Algorithm 2: Function SRNCDIJKSTRA, Algorithm 3: Full Dynamic Controllability Checking Algorithm, Algorithm 4: Algorithm for finding potential function, from [Cairo et al., 2018], Algorithm 5: Algorithm for finding potential function, from [Goldberg, 1995]. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that source code for the described methodology is open-source or publicly available. |
| Open Datasets | No | This paper is theoretical in nature and does not describe the use of specific datasets, thus no information on dataset availability or access is provided. |
| Dataset Splits | No | This paper focuses on theoretical algorithm analysis and does not involve empirical data or dataset splits for training or validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper describes algorithms but does not specify any software dependencies with version numbers required for replication. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm analysis, thus it does not describe experimental setup details like hyperparameters or training settings. |