Publication at Faculty of Mathematics and Physics |
2008
Abstract
Temporal Networks with Alternatives were proposed to model alternative and parallel processes in planning and scheduling applications. However the problem of deciding which nodes can be consistently included in such networks is NP-complete.
In this paper we study a tractable subclass of Temporal Networks with Alternatives that covers a wide range of real-life processes, while the problem of deciding node validity is solvable in polynomial time. We also present an algorithm that can effectively recognize whether a given network belongs to the proposed sub-class.