{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:16:34Z","timestamp":1758824194892},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_26","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"299-310","source":"Crossref","is-referenced-by-count":9,"title":["Scheduling Partially Ordered Jobs Faster Than\u00a02 n"],"prefix":"10.1007","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","reference":[{"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. Accepted for Publication in Journal of Discrete Algorithms (2011)","key":"26_CR1"},{"key":"26_CR2","first-page":"173","volume-title":"51st 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: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 173\u2013182. IEEE Computer Society, Los Alamitos (2010)"},{"doi-asserted-by":"crossref","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)","key":"26_CR3","DOI":"10.1145\/1250790.1250801"},{"issue":"2","key":"26_CR4","doi-asserted-by":"publisher","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-exclusion. SIAM J. Comput.\u00a039(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"26_CR5","doi-asserted-by":"publisher","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 Applied Mathematics\u00a098(1-2), 29\u201338 (1999)","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","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. CoRR abs\/1103.0534 (2011)","key":"26_CR6","DOI":"10.1109\/FOCS.2011.23"},{"issue":"40-42","key":"26_CR7","doi-asserted-by":"publisher","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.\u00a0411(40-42), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-13731-0_8","volume-title":"Algorithm Theory - SWAT 2010","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than o(2n). In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol.\u00a06139, pp. 74\u201380. Springer, Heidelberg (2010)"},{"key":"26_CR9","doi-asserted-by":"publisher","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, Heidelberg (2010)"},{"issue":"5","key":"26_CR10","doi-asserted-by":"publisher","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\u00a056(5), 1\u201332 (2009)","journal-title":"J. ACM"},{"issue":"2","key":"26_CR11","doi-asserted-by":"publisher","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.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Kan, A.R.: Complexity of scheduling under precedence constraints. Operations Research\u00a026, 22\u201335 (1978)","journal-title":"Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 777\u2013789 (2011)","key":"26_CR13","DOI":"10.1137\/1.9781611973082.61"},{"issue":"6","key":"26_CR14","doi-asserted-by":"publisher","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. Operations Research\u00a051(6), 981\u2013992 (2003)","journal-title":"Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: 45th Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013255 (2004)","key":"26_CR15","DOI":"10.1109\/FOCS.2004.40"},{"doi-asserted-by":"crossref","unstructured":"Patrascu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1065\u20131075 (2010)","key":"26_CR16","DOI":"10.1137\/1.9781611973075.86"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"Algorithms - ESA 2009","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: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 554\u2013565. Springer, Heidelberg (2009)"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-540-28639-4_25","volume-title":"Parameterized and Exact Computation","author":"G.J. Woeginger","year":"2004","unstructured":"Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems (Invited talk). In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 281\u2013290. Springer, Heidelberg (2004)"},{"issue":"3","key":"26_CR19","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0156(3), 397\u2013405 (2008)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:07:52Z","timestamp":1560514072000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}