Nested Temporal Networks with Alternatives: Recognition and Tractability

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100209" target="_blank" >RIV/00216208:11320/08:00100209 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Nested Temporal Networks with Alternatives: Recognition and Tractability
Original language description
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 paperwe 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 recognizewhether a given network belongs to the proposed sub-class.
Czech name
Zahnízděné temporální sítě s alternativami: rozpoznání a složitost
Czech description
Článek navrhuje formální model pro alternativní a paralelní procesy, popisuje jak lze tento model rozpoznat a jaká je složitost výběru uzlů v tomto modelu.

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Applied Computing 2008 - Proceedings of 23rd Annual ACM Symposium on Applied Computing
ISBN
978-1-59593-753-7
ISSN
—
e-ISSN
—
Number of pages
2
Pages from-to
—
Publisher name
ACM
Place of publication
Fortaleza
Event location
Fortaleza
Event date
Jan 1, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)