{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:13:23Z","timestamp":1767262403103,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,4,7]],"date-time":"2021-04-07T00:00:00Z","timestamp":1617753600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CNS-1814739"],"award-info":[{"award-number":["CNS-1814739"]}]},{"name":"National Science Foundation","award":["CPS-1932530"],"award-info":[{"award-number":["CPS-1932530"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,4,7]]},"DOI":"10.1145\/3453417.3453422","type":"proceedings-article","created":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T22:18:55Z","timestamp":1626992335000},"page":"165-172","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard"],"prefix":"10.1145","author":[{"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[{"name":"Washington University in St. Louis, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,7,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Baker and Dan Trietsch","author":"R.","year":"2009","unstructured":"Kenneth\u00a0 R. Baker and Dan Trietsch . 2009 . Principles of Sequencing and Scheduling. Wiley Publishing . Kenneth\u00a0R. Baker and Dan Trietsch. 2009. Principles of Sequencing and Scheduling. Wiley Publishing."},{"volume-title":"Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol.\u00a0185","author":"Barrett W.","key":"e_1_3_2_1_2_1","unstructured":"Clark\u00a0 W. Barrett , Roberto Sebastiani , Sanjit\u00a0 A. Seshia , and Cesare Tinelli . 2009. Satisfiability Modulo Theories . In Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol.\u00a0185 . IOS Press , 825\u2013885. https:\/\/doi.org\/10.3233\/978-1-58603-929-5-825 10.3233\/978-1-58603-929-5-825 Clark\u00a0W. Barrett, Roberto Sebastiani, Sanjit\u00a0A. Seshia, and Cesare Tinelli. 2009. Satisfiability Modulo Theories. In Handbook of Satisfiability, Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh (Eds.). Frontiers in Artificial Intelligence and Applications, Vol.\u00a0185. IOS Press, 825\u2013885. https:\/\/doi.org\/10.3233\/978-1-58603-929-5-825"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829061"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394810.3394813"},{"volume-title":"Multiprocessor Scheduling for Real-Time Systems","author":"Baruah Sanjoy","key":"e_1_3_2_1_5_1","unstructured":"Sanjoy Baruah , Marko Bertogna , and Giorgio Buttazzo . 2015. Multiprocessor Scheduling for Real-Time Systems . Springer Publishing Company, Inc orporated. Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. 2015. Multiprocessor Scheduling for Real-Time Systems. Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.27"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.59"},{"volume-title":"Proceedings of the 11th Real-Time Systems Symposium. IEEE Computer Society Press","author":"Baruah S.","key":"e_1_3_2_1_8_1","unstructured":"S. Baruah , A. Mok , and L. Rosier . 1990. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor . In Proceedings of the 11th Real-Time Systems Symposium. IEEE Computer Society Press , Orlando, Florida, 182\u2013190. S. Baruah, A. Mok, and L. Rosier. 1990. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor. In Proceedings of the 11th Real-Time Systems Symposium. IEEE Computer Society Press, Orlando, Florida, 182\u2013190."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1214341"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90142-2"},{"volume-title":"Complexity of Computer Computations, R.\u00a0Miller and J.\u00a0Thatcher (Eds.)","author":"Karp R.","key":"e_1_3_2_1_13_1","unstructured":"R. Karp . 1972. Reducibility Among Combinatorial Problems . In Complexity of Computer Computations, R.\u00a0Miller and J.\u00a0Thatcher (Eds.) . Plenum Press , New York , 85\u2013103. R. Karp. 1972. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, R.\u00a0Miller and J.\u00a0Thatcher (Eds.). Plenum Press, New York, 85\u2013103."},{"volume-title":"A Practitioner\u2019s Handbook for Real-time Analysis","author":"Klein H.","key":"e_1_3_2_1_14_1","unstructured":"Mark\u00a0 H. Klein , Thomas Ralya , Bill Pollak , Ray Obenza , and Michael\u00a0Gonz\u00e1lez Harbour . 1993. A Practitioner\u2019s Handbook for Real-time Analysis . Kluwer Academic Publishers, Norwell, MA , USA. Mark\u00a0H. Klein, Thomas Ralya, Bill Pollak, Ray Obenza, and Michael\u00a0Gonz\u00e1lez Harbour. 1993. A Practitioner\u2019s Handbook for Real-time Analysis. Kluwer Academic Publishers, Norwell, MA, USA."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_3_2_1_17_1","volume-title":"On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS).","author":"Marchetti-Spaccamela Alberto","year":"2020","unstructured":"Alberto Marchetti-Spaccamela , Nicole Megow , Jens Schl\u00f6ter , Martin Skutella , and Leen Stougie . 2020 . On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS). Alberto Marchetti-Spaccamela, Nicole Megow, Jens Schl\u00f6ter, Martin Skutella, and Leen Stougie. 2020. On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems. In IEEE International Parallel and Distributed Processing Symposium (IPDPS)."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.26"},{"volume-title":"Proceedings of the 17th Real-Time Systems Symposium. IEEE Computer Society Press","author":"K.","key":"e_1_3_2_1_19_1","unstructured":"Aloysius\u00a0 K. Mok and Deji Chen. 1996. A multiframe model for real-time tasks . In Proceedings of the 17th Real-Time Systems Symposium. IEEE Computer Society Press , Washington, DC. Aloysius\u00a0K. Mok and Deji Chen. 1996. A multiframe model for real-time tasks. In Proceedings of the 17th Real-Time Systems Symposium. IEEE Computer Society Press, Washington, DC."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2011.15"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80008-0"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"},{"key":"e_1_3_2_1_25_1","unstructured":"Houssam-Eddine Zahaf Nicola Capodieci Roberto Cavicchioli Marko Bertogna and Giuseppe Lipari. 2019. A C-DAG task model for scheduling complex real-time tasks on heterogeneous platforms: Preemption matters. arxiv:1901.02450\u00a0[cs.OS] arXiv.  Houssam-Eddine Zahaf Nicola Capodieci Roberto Cavicchioli Marko Bertogna and Giuseppe Lipari. 2019. A C-DAG task model for scheduling complex real-time tasks on heterogeneous platforms: Preemption matters. arxiv:1901.02450\u00a0[cs.OS] arXiv."}],"event":{"name":"RTNS'2021: 29th International Conference on Real-Time Networks and Systems","acronym":"RTNS'2021","location":"NANTES France"},"container-title":["29th International Conference on Real-Time Networks and Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453417.3453422","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453417.3453422","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453417.3453422","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:06Z","timestamp":1750197786000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453417.3453422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,7]]},"references-count":23,"alternative-id":["10.1145\/3453417.3453422","10.1145\/3453417"],"URL":"https:\/\/doi.org\/10.1145\/3453417.3453422","relation":{},"subject":[],"published":{"date-parts":[[2021,4,7]]},"assertion":[{"value":"2021-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}