{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:45:23Z","timestamp":1742957123833,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030420703"},{"type":"electronic","value":"9783030420710"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-42071-0_11","type":"book-chapter","created":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T17:02:44Z","timestamp":1587574964000},"page":"145-164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1848-0076","authenticated-orcid":false,"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, R.R.: Probabilistic rank and matrix rigidity. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 641\u2013652 (2017)","DOI":"10.1145\/3055399.3055484"},{"key":"11_CR2","unstructured":"Abboud, A., Williams, R.R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4\u20136 January 2015, pp. 218\u2013230 (2015)"},{"issue":"4","key":"11_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"key":"11_CR5","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften, vol. 315. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-662-03338-8"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Bansal, N., Eli\u00e1s, M., Koumoutsos, G., Nederlof, J.: Competitive algorithms for generalized k-server in uniform metrics. In: Czumaj, A., (ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 992\u20131001. SIAM (2018)","DOI":"10.1137\/1.9781611975031.64"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-04128-0_52","volume-title":"Algorithms - ESA 2009","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 578\u2013586. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04128-0_52"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","volume":"87","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87, 119\u2013139 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Kratsch, S., Nederlof, J.: Fast Hamiltonicity checking via bases of perfect matchings. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 301\u2013310 (2013)","DOI":"10.1145\/2488608.2488646"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Lindzey, N., Nederlof, J.: A tight lower bound for counting Hamiltonian cycles via matrix rank. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 1080\u20131099 (2018)","DOI":"10.1137\/1.9781611975031.70"},{"key":"11_CR12","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. In: Ostrovsky, R. (ed.), IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 150\u2013159. IEEE Computer Society (2011)","DOI":"10.1109\/FOCS.2011.23"},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","journal-title":"J. ACM"},{"key":"11_CR14","unstructured":"Freivalds, R.: Probabilistic machines can use less running time. In: Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, 8\u201312 August 1977, pp. 839\u2013842 (1977)"},{"key":"11_CR15","unstructured":"Jansen, B.M.P., Nederlof, J.: Computing the chromatic number using graph decompositions via matrix rank. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, ESA 2018, 20\u201322 August 2018, Helsinki, Finland. LIPIcs, vol. 112, pp. 47:1\u201347:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"11_CR16","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/2635810","volume":"10","author":"S Kratsch","year":"2014","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. ACM Trans. Algorithms 10(4), 20:1\u201320:15 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/3170444","volume":"14","author":"D Lokshtanov","year":"2018","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. ACM Trans. Algorithms 14(2), 14:1\u201314:20 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"11_CR19","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(01)00185-5","volume":"81","author":"VV Lozin","year":"2002","unstructured":"Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inf. Process. Lett. 81(1), 7\u201311 (2002)","journal-title":"Inf. Process. Lett."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.E.: Lattices, M\u00f6bius functions and communication complexity. In: 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24\u201326 October 1988, pp. 81\u201390. IEEE Computer Society (1988)","DOI":"10.1109\/SFCS.1988.21924"},{"key":"11_CR21","volume-title":"Thirty-Three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra","author":"J Matou\u0161ek","year":"2010","unstructured":"Matou\u0161ek, J.: Thirty-Three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, vol. 53. American Mathematical Society, Providence (2010)"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0304-0208(08)73110-4","volume":"109","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. North-Holland Math. Stud. 109, 239\u2013254 (1985). Analysis and Design of Algorithms for Combinatorial Problems","journal-title":"North-Holland Math. Stud."},{"key":"11_CR23","unstructured":"Nederlof, J.: Faster subset sum via improved orthogonal vectors (2017). http:\/\/www.win.tue.nl\/~jnederlo\/problem.pdf"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Nederlof, J.: Bipartite TSP in $$O(1.9999^n)$$ time, assuming quadratic time matrix multiplication (2019). Unpublished","DOI":"10.1145\/3357713.3384264"},{"key":"11_CR25","unstructured":"Pratt, K.: Faster algorithms via waring decompositions. In: The Proceedings of FOCS 2018 (2018, to appear)"},{"issue":"4","key":"11_CR26","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/BF01192528","volume":"15","author":"R Raz","year":"1995","unstructured":"Raz, R., Spieker, B.: On the \u201clog rank\u201d-conjecture in communication complexity. Combinatorica 15(4), 567\u2013588 (1995)","journal-title":"Combinatorica"},{"key":"11_CR27","unstructured":"Williams, R.: The polynomial method in circuit complexity applied to algorithm design (invited talk). In: Raman, V., Suresh, S.P. (eds.), 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, 15\u201317 December 2014, New Delhi, India. LIPIcs, vol. 29, pp. 47\u201360. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"3","key":"11_CR28","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S0097539702407345","volume":"32","author":"R de Wolf","year":"2003","unstructured":"de Wolf, R.: Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32(3), 681\u2013699 (2003)","journal-title":"SIAM J. Comput."},{"key":"11_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1037","DOI":"10.1007\/978-3-662-48350-3_86","volume-title":"Algorithms - ESA 2015","author":"M Zehavi","year":"2015","unstructured":"Zehavi, M.: Mixing color coding-related techniques. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 1037\u20131049. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_86"}],"container-title":["Lecture Notes in Computer Science","Treewidth, Kernels, and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-42071-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,30]],"date-time":"2023-09-30T06:51:28Z","timestamp":1696056688000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-42071-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030420703","9783030420710"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-42071-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}