id:"swepub:oai:DiVA.org:uu-436118"
Sökning: id:"swepub:oai:DiVA.org:uu-436118" > On the Volume Calcu...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
- Sun, JinghaoNortheastern Univ, Shenyang, Peoples R China. (författare)
On the Volume Calculation for Conditional DAG Tasks : Hardness and Algorithms
- Artikel/kapitelEngelska2020
Förlag, utgivningsår, omfång ...
- NEW YORK, USA,2020
- printrdacarrier
Nummerbeteckningar
- LIBRIS-ID:oai:DiVA.org:uu-436118
- https://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-436118URI
- https://doi.org/10.23919/DATE48585.2020.9116559DOI
- https://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-432004URI
Kompletterande språkuppgifter
- Språk:engelska
- Sammanfattning på:engelska
Ingår i deldatabas
- SwePubSwePub
Klassifikation
Anmärkningar
- 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 och genrebeteckningar
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- DAG
- Conditional branches
- Volume
- NP-hard
Biuppslag (personer, institutioner, konferenser, titlar ...)
- Chi, YaoyaoNortheastern Univ, Shenyang, Peoples R China. (författare)
- Xu, TianfeiNortheastern Univ, Shenyang, Peoples R China. (författare)
- Cao, LeiNortheastern Univ, Shenyang, Peoples R China. (författare)
- Guan, NanHong Kong Polytech Univ, Hong Kong, Peoples R China. (författare)
- Guo, ZhishanUniv Cent Florida, Orlando, FL 32816 USA. (författare)
- Wang, YiUppsala universitet,Datorteknik(Swepub:uu)wangyi (författare)
- Northeastern Univ, Shenyang, Peoples R China.Hong Kong Polytech Univ, Hong Kong, Peoples R China. (creator_code:org_t)
Sammanhörande titlar
- Ingår i:PROCEEDINGS OF THE 2020 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION (DATE 2020)NEW YORK, USA, s. 204-2099783981926347
Internetlänk
Hitta via bibliotek
- PROCEEDINGS OF THE 2020 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE &... (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Sun, Jinghao
- Chi, Yaoyao
- Xu, Tianfei
- Cao, Lei
- Guan, Nan
- Guo, Zhishan
- visa fler...
- Wang, Yi
- visa färre...
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- och Datavetenskap
- Artiklar i publikationen
- PROCEEDINGS OF T ...
- Av lärosätet
- Uppsala universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
