Resource Temporal Networks: Definition and Complexity
Abstract
This paper introduces the concept of Resource Temporal Network (RTN), a constraint network that subsumes both classical attributes used in A.I. Planning and capacity resources traditionally handled in Scheduling. After giving a formal definition of RTNs, we analyze their expressive power and study complexities of several fragments of the RTN framework. We show that solving an RTN is in general NP-Complete - which is not surprising given the expressivity of the framework - whereas computing a Necessary Truth Criterion is polynomial. This last result opens the door for promising algorithms to solve RTNs.
Cite
Text
Laborie. "Resource Temporal Networks: Definition and Complexity." International Joint Conference on Artificial Intelligence, 2003. doi:10.1038/nm0806-884Markdown
[Laborie. "Resource Temporal Networks: Definition and Complexity." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/laborie2003ijcai-resource/) doi:10.1038/nm0806-884BibTeX
@inproceedings{laborie2003ijcai-resource,
title = {{Resource Temporal Networks: Definition and Complexity}},
author = {Laborie, Philippe},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2003},
pages = {948-953},
doi = {10.1038/nm0806-884},
url = {https://mlanthology.org/ijcai/2003/laborie2003ijcai-resource/}
}