Zahnízděné temporální sítě s alternativami: rozpoznání a složitost

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Nested Temporal Networks with Alternatives: Recognition and Tractability

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Nested Temporal Networks with Alternatives: Recognition and Tractability

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

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

Název statě ve sborníku

Applied Computing 2008 - Proceedings of 23rd Annual ACM Symposium on Applied Computing

ISBN

978-1-59593-753-7

ISSN

—

e-ISSN

—

Počet stran výsledku

2

Strana od-do

—

Název nakladatele

ACM

Místo vydání

Fortaleza

Místo konání akce

Fortaleza

Datum konání akce

1. 1. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—