{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:52:45Z","timestamp":1780051965177,"version":"3.53.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s00453-012-9630-x","type":"journal-article","created":{"date-parts":[[2012,3,9]],"date-time":"2012-03-09T16:02:12Z","timestamp":1331308932000},"page":"868-884","source":"Crossref","is-referenced-by-count":48,"title":["Fast Polynomial-Space Algorithms Using Inclusion-Exclusion"],"prefix":"10.1007","volume":"65","author":[{"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,3,10]]},"reference":[{"key":"9630_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/978-3-642-02927-1_8","volume-title":"Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Part I","author":"O. Amini","year":"2009","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting subgraphs via homomorphisms. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Part I. Lecture Notes in Computer Science, vol. 5555, pp. 71\u201382. Springer, Berlin (2009)"},{"issue":"2","key":"9630_CR2","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2), 226\u2013249 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"9630_CR3","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-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"9630_CR4","first-page":"67","volume-title":"Proceedings of the 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: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 67\u201374. ACM, New York (2007)"},{"key":"9630_CR5","first-page":"677","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (STOC)","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (STOC), pp. 677\u2013686. IEEE Comput. Soc., Los Alamitos (2008)"},{"issue":"3","key":"9630_CR6","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00224-009-9185-7","volume":"47","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Trimmed Moebius inversion and graphs of bounded degree. Theory Comput. Syst. 47(3), 637\u2013654 (2010)","journal-title":"Theory Comput. Syst."},{"key":"9630_CR7","unstructured":"Bodlaender, H.L., Kratsch, D.: An exact algorithm for graph coloring with polynomial memory. Technical Report UU-CS-2006-015, Department of Information and Computing Sciences, Utrecht University (2006)"},{"issue":"2","key":"9630_CR8","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1006\/jctb.1995.1055","volume":"65","author":"F.R.K. Chung","year":"1995","unstructured":"Chung, F.R.K., Graham, R.L.: On the cover polynomial of a digraph. J. Comb. Theory, Ser. B 65(2), 273\u2013290 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9630_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1972). doi: 10.1002\/net.3230010302","journal-title":"Networks"},{"key":"9630_CR10","series-title":"Lecture Notes in Computer Science","first-page":"100","volume-title":"Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Gaspers, S., Raible, D.: Exact and parameterized algorithms for max internal spanning tree. In: Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 5911, pp. 100\u2013111. Springer, Berlin (2009)"},{"key":"9630_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/978-3-540-87744-8_36","volume-title":"Proceedings of the 16th Annual European Symposium on Algorithms (ESA)","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Faster Steiner tree computation in polynomial-space. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 5193, pp. 430\u2013441. Springer, Berlin (2008)"},{"issue":"3","key":"9630_CR12","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"B. Fuchs","year":"2007","unstructured":"Fuchs, B., Kern, W., M\u00f6lle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41(3), 493\u2013500 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9630_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/978-3-540-79228-4_42","volume-title":"Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC)","author":"S. Gaspers","year":"2008","unstructured":"Gaspers, S., Saurabh, S., Stepanov, A.A.: A moderately exponential time algorithm for full degree spanning tree. In: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC). Lecture Notes in Computer Science, vol. 4978, pp. 479\u2013489. Springer, Berlin (2008)"},{"key":"9630_CR14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1, 49\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9630_CR15","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/800179.810218","volume-title":"Proceedings of the 1977 Annual Conference (ACM)","author":"S. Kohn","year":"1977","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the traveling salesman problem. In: Proceedings of the 1977 Annual Conference (ACM), pp. 294\u2013300. ACM, New York (1977). doi: 10.1145\/800179.810218"},{"key":"9630_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-642-11269-0_21","volume-title":"Proceedings of the 4th International Workshop Parameterized and Exact Computation (IWPEC)","author":"M. Koivisto","year":"2009","unstructured":"Koivisto, M.: Partitioning into sets of bounded cardinality. In: Proceedings of the 4th International Workshop Parameterized and Exact Computation (IWPEC). Lecture Notes in Computer Science, vol. 5917, pp. 258\u2013263. Springer, Berlin (2009)"},{"key":"9630_CR17","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/1806689.1806735","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)","author":"D. Lokshtanov","year":"2010","unstructured":"Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 321\u2013330. ACM, New York (2010)"},{"key":"9630_CR18","unstructured":"Nederlof, J.: Inclusion exclusion for hard problems. Master\u2019s thesis, Utrecht University (August 2008)"},{"key":"9630_CR19","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/978-3-540-79228-4_43","volume-title":"Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC)","author":"O. Ponta","year":"2008","unstructured":"Ponta, O., H\u00fcffner, F., Niedermeier, R.: Speeding up dynamic programming for some $\\mathcal{NP}$ -hard graph recoloring problems. In: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 490\u2013501. Springer, Berlin (2008)"},{"key":"9630_CR20","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)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9630-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T15:26:36Z","timestamp":1497972396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9630-x"}},"subtitle":["Improving on Steiner Tree and Related Problems"],"short-title":[],"issued":{"date-parts":[[2012,3,10]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9630"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9630-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,10]]}}}