Sökning: id:"swepub:oai:DiVA.org:uu-436118" >
On the Volume Calcu...
On the Volume Calculation for Conditional DAG Tasks : Hardness and Algorithms
-
- Sun, Jinghao (författare)
- Northeastern Univ, Shenyang, Peoples R China.
-
- Chi, Yaoyao (författare)
- Northeastern Univ, Shenyang, Peoples R China.
-
- Xu, Tianfei (författare)
- Northeastern Univ, Shenyang, Peoples R China.
-
visa fler...
-
- Cao, Lei (författare)
- Northeastern Univ, Shenyang, Peoples R China.
-
- Guan, Nan (författare)
- Hong Kong Polytech Univ, Hong Kong, Peoples R China.
-
- Guo, Zhishan (författare)
- Univ Cent Florida, Orlando, FL 32816 USA.
-
- Wang, Yi (författare)
- Uppsala universitet,Datorteknik
-
visa färre...
-
Northeastern Univ, Shenyang, Peoples R China Hong Kong Polytech Univ, Hong Kong, Peoples R China. (creator_code:org_t)
- NEW YORK, USA, 2020
- 2020
- Engelska.
-
Ingår i: PROCEEDINGS OF THE 2020 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE 2020). - NEW YORK, USA. - 9783981926347 ; , s. 204-209
- Relaterad länk:
-
https://doi.org/10.2...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.2...
-
https://urn.kb.se/re...
-
visa färre...
Abstract
Ämnesord
Stäng
- The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly NP-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- DAG
- Conditional branches
- Volume
- NP-hard
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas