{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T15:09:15Z","timestamp":1767452955794},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9694-7","type":"journal-article","created":{"date-parts":[[2012,10,8]],"date-time":"2012-10-08T16:04:42Z","timestamp":1349712282000},"page":"692-714","source":"Crossref","is-referenced-by-count":6,"title":["Scheduling Partially Ordered Jobs Faster than 2 n"],"prefix":"10.1007","volume":"68","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,10,9]]},"reference":[{"issue":"3","key":"9694_CR1","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/j.jda.2011.03.002","volume":"9","author":"D. Binkele-Raible","year":"2011","unstructured":"Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the 2 n -barrier for irredundance: Two lines of attack. J. Discrete Algorithms 9(3), 214\u2013230 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"9694_CR2","first-page":"173","volume-title":"51th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 173\u2013182. IEEE Comput. Soc., Los Alamitos (2010)"},{"key":"9694_CR3","first-page":"67","volume-title":"39th Annual ACM Symposium on Theory of Computing (STOC)","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 67\u201374 (2007). doi: 10.1145\/1250790.1250801"},{"issue":"2","key":"9694_CR4","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"9694_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03612-9","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"1998","unstructured":"Brucker, P.: Scheduling Algorithms, 2nd edn. Springer, Heidelberg (1998)","edition":"2"},{"issue":"1-2","key":"9694_CR6","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0166-218X(98)00143-7","volume":"98","author":"C. Chekuri","year":"1999","unstructured":"Chekuri, C., Motwani, R.: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Appl. Math. 98(1-2), 29\u201338 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9694_CR7","first-page":"150","volume-title":"52nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 150\u2013159. IEEE Press, New York (2011)"},{"issue":"40-42","key":"9694_CR8","doi-asserted-by":"crossref","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40-42), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9694_CR9","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1016\/j.ipl.2011.09.004","volume":"111","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than O(2 n ). Inf. Process. Lett. 111, 1099\u20131103 (2011)","journal-title":"Inf. Process. Lett."},{"key":"9694_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F. Fomin","year":"2010","unstructured":"Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"issue":"5","key":"9694_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 1\u201332 (2009). doi: 10.1145\/1552285.1552286","journal-title":"J. ACM"},{"key":"9694_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-23719-5_25","volume-title":"19th Annual European Symposium on Algorithms (ESA)","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Exact algorithm for the maximum induced planar subgraph problem. In: 19th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 6942, pp. 287\u2013298. Springer, Berlin (2011)"},{"key":"9694_CR13","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. Graham","year":"1966","unstructured":"Graham, R.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9694_CR14","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1287\/moor.7.3.354","volume":"7","author":"N. Hefetz","year":"1982","unstructured":"Hefetz, N., Adiri, I.: An efficient optimal algorithm for the two-machines unit-time jobshop schedule-length problem. Math. Oper. Res. 7, 354\u2013360 (1982)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"9694_CR15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9694_CR16","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/mnsc.19.5.544","volume":"19","author":"E.L. Lawler","year":"1973","unstructured":"Lawler, E.L.: Optimal sequencing of a single machine subject to precedence constraints. Manag. Sci. 19, 544\u2013546 (1973)","journal-title":"Manag. Sci."},{"key":"9694_CR17","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J.K. Lenstra","year":"1977","unstructured":"Lenstra, J.K., Kan, A.H.G.R., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343\u2013362 (1977)","journal-title":"Ann. Discrete Math."},{"key":"9694_CR18","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Kan, A.H.G.R.: Complexity of scheduling under precedence constraints. Oper. Res. 26, 22\u201335 (1978)","journal-title":"Oper. Res."},{"key":"9694_CR19","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/1.9781611973082.61","volume-title":"Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 777\u2013789 (2011)"},{"issue":"6","key":"9694_CR20","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1287\/opre.51.6.981.24912","volume":"51","author":"F. Margot","year":"2003","unstructured":"Margot, F., Queyranne, M., Wang, Y.: Decompositions, network flows, and a precedence constrained single-machine scheduling problem. Oper. Res. 51(6), 981\u2013992 (2003)","journal-title":"Oper. Res."},{"key":"9694_CR21","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/FOCS.2004.40","volume-title":"45th Symposium on Foundations of Computer Science (FOCS)","author":"M. Mucha","year":"2004","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: 45th Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013255. IEEE Comput. Soc., Los Alamitos (2004)"},{"key":"9694_CR22","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/1.9781611973075.86","volume-title":"Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Patrascu","year":"2010","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1065\u20131075 (2010)"},{"key":"9694_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"17th Annual European Symposium (ESA)","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets measure and conquer. In: 17th Annual European Symposium (ESA). Lecture Notes in Computer Science, vol. 5757, pp. 554\u2013565. Springer, Berlin (2009)"},{"key":"9694_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-540-28639-4_25","volume-title":"First International Workshop on Parameterized and Exact Computation (IWPEC)","author":"G.J. Woeginger","year":"2004","unstructured":"Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems (invited talk). In: First International Workshop on Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 3162, pp. 281\u2013290. Springer, Berlin (2004)"},{"issue":"3","key":"9694_CR25","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.dam.2007.03.023","volume":"156","author":"G.J. Woeginger","year":"2008","unstructured":"Woeginger, G.J.: Open problems around exact algorithms. Discrete Appl. Math. 156(3), 397\u2013405 (2008)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9694-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T01:08:00Z","timestamp":1498007280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9694-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9694"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9694-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,9]]}}}