Resource Temporal Networks: Definition and Complexity
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 948-952.
Abstract
This paper introduces the concept of Resource Temporal Network (RTN), a constraint network that subsumes both classical attributes used in A.l. 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.
@inproceedings{ijcai2003p136,
title = {Resource Temporal Networks: Definition and Complexity},
author = {Laborie, Philippe},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {948--952},
year = {2003},
url = {https://ijcai.org/proceedings/2003/136},
}
TY - CPAPER TI - Resource Temporal Networks: Definition and Complexity AU - Laborie, Philippe T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 948 EP - 952 UR - https://ijcai.org/proceedings/2003/136 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
