{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T05:02:52Z","timestamp":1771045372250,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s11241-022-09380-z","type":"journal-article","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T23:04:00Z","timestamp":1648508640000},"page":"134-152","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Feasibility analysis for HPC-DAG tasks"],"prefix":"10.1007","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4541-3445","authenticated-orcid":false,"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,26]]},"reference":[{"key":"9380_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity\u2014a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B (2009) Computational complexity\u2014a modern approach. Cambridge University Press, Cambridge"},{"key":"9380_CR2","doi-asserted-by":"crossref","unstructured":"Baruah S (2021) Feasibility analysis of conditional DAG tasks is co-$$\\rm NP^{\\text{NP}}$$-hard (why this matters). In: Proceedings of the twenty-ninth international conference on real-time and network systems, RTNS \u201921, New York, NY, USA. ACM","DOI":"10.1145\/3453417.3453422"},{"key":"#cr-split#-9380_CR3.1","doi-asserted-by":"crossref","unstructured":"Baruah S, Marchetti-Spaccamela A (2021) Feasibility analysis of conditional DAG tasks. In: Brandenburg BB","DOI":"10.1145\/3453417.3453422"},{"key":"#cr-split#-9380_CR3.2","unstructured":"(ed) 33rd Euromicro conference on real-time systems (ECRTS 2021), vol 196. Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 12:1-12:17"},{"key":"9380_CR4","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A, Stougie L, Wiese A (2012) A generalized parallel task model for recurrent real-time processes. In: Proceedings of the IEEE real-time systems symposium, RTSS 2012, San Juan, Puerto Rico, pp 63\u201372","DOI":"10.1109\/RTSS.2012.59"},{"key":"9380_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08696-5","volume-title":"Multiprocessor scheduling for real-time systems","author":"S Baruah","year":"2015","unstructured":"Baruah S, Bertogna M, Buttazzo G (2015) Multiprocessor scheduling for real-time systems. Springer Publishing Company Incorporated, New York"},{"key":"9380_CR6","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A (2015) The global EDF scheduling of systems of conditional sporadic DAG tasks. In: Proceedings of the 2014 26th Euromicro conference on real-time systems, ECRTS \u201915, Lund (Sweden). IEEE Computer Society Press, pp 222\u2013231","DOI":"10.1109\/ECRTS.2015.27"},{"key":"9380_CR7","doi-asserted-by":"crossref","unstructured":"Fonseca J, Nelis V, Raravi G, Pinho LM. A multi-DAG model for real-time parallel applications with conditional execution. In: Proceedings of the ACM\/ SIGAPP symposium on applied computing (SAC), Salamanca, Spain, April (2015). ACM Press","DOI":"10.1145\/2695664.2695808"},{"key":"9380_CR8","first-page":"1747","volume":"70","author":"Z Houssam-Eddine","year":"2020","unstructured":"Houssam-Eddine Z, Capodieci N, Cavicchioli R, Bertogna M, Lipari G (2020) The HPC-DAG task model for heterogeneous real-time systems. IEEE Trans Comput 70:1747\u20131761","journal-title":"IEEE Trans Comput"},{"issue":"3","key":"9380_CR9","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(94)90142-2","volume":"52","author":"J Klaus","year":"1994","unstructured":"Klaus J (1994) Analysis of scheduling problems with typed task systems. Discret Appl Math 52(3):223\u2013232","journal-title":"Discret Appl Math"},{"key":"9380_CR10","doi-asserted-by":"crossref","unstructured":"Melani A, Bertogna M, Bonifaci V, Marchetti-Spaccamela A, Buttazzo G (2015) Response-time analysis of conditional DAG tasks in multiprocessor systems. In: Proceedings of the 2014 26th Euromicro conference on real-time systems, ECRTS \u201915, Lund (Sweden). IEEE Computer Society Press, pp 222\u2013231","DOI":"10.1109\/ECRTS.2015.26"},{"key":"9380_CR11","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading, MA"},{"key":"9380_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L Stockmeyer","year":"1976","unstructured":"Stockmeyer L (1976) The polynomial-time hierarchy. Theoret Comput Sci 3:1\u201322","journal-title":"Theoret Comput Sci"},{"key":"9380_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C Wrathall","year":"1976","unstructured":"Wrathall C (1976) Complete sets and the polynomial-time hierarchy. Theoret Comput Sci 3:23\u201333","journal-title":"Theoret Comput Sci"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-022-09380-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-022-09380-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-022-09380-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T20:09:48Z","timestamp":1653163788000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-022-09380-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,26]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9380"],"URL":"https:\/\/doi.org\/10.1007\/s11241-022-09380-z","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,26]]},"assertion":[{"value":"7 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}