{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T02:01:36Z","timestamp":1790215296237,"version":"4.1.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030752415","type":"print"},{"value":"9783030752422","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-75242-2_16","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"231-244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Multistage View on 2-Satisfiability"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2203-4386","authenticated-orcid":false,"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"issue":"3","key":"16_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90002-4","journal-title":"Inf. Process. Lett."},{"key":"16_CR2","unstructured":"Bampis, E., Escoffier, B., Kononov, A.V.: LP-based algorithms for multistage minimization problems. CoRR abs\/1909.10354 (2019). http:\/\/arxiv.org\/abs\/1909.10354"},{"key":"16_CR3","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Lampis, M., Paschos, V.T.: Multistage matchings. In: Proceedings of 16th SWAT. LIPIcs, vol. 101, pp. 7:1\u20137:13. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.7","DOI":"10.4230\/LIPIcs.SWAT.2018.7"},{"key":"16_CR4","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Schewior, K., Teiller, A.: Online multistage subset maximization problems. In: Proceedings of 27th ESA. LIPIcs, vol. 144, pp. 11:1\u201311:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.11","DOI":"10.4230\/LIPIcs.ESA.2019.11"},{"key":"16_CR5","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Teiller, A.: Multistage knapsack. In: Proceedings of 44th MFCS. LIPIcs, vol. 138, pp. 22:1\u201322:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.22","DOI":"10.4230\/LIPIcs.MFCS.2019.22"},{"issue":"8","key":"16_CR6","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009). https:\/\/doi.org\/10.1016\/j.jcss.2009.04.001","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR7","unstructured":"Bredereck, R., Fluschnik, T., Kaczmarczyk, A.: Multistage committee election. CoRR abs\/2005.02300 (2020). https:\/\/arxiv.org\/abs\/2005.02300"},{"issue":"8","key":"16_CR8","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006). https:\/\/doi.org\/10.1016\/j.jcss.2006.04.007","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR9","unstructured":"Chimani, M., Troost, N., Wiedera, T.: Approximating multistage matching problems. CoRR abs\/2002.06887 (2020). https:\/\/arxiv.org\/abs\/2002.06887"},{"issue":"6","key":"16_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0020-0190(99)00025-3","volume":"69","author":"M Chrobak","year":"1999","unstructured":"Chrobak, M., D\u00fcrr, C.: Reconstructing hv-convex polyominoes from orthogonal projections. Inf. Process. Lett. 69(6), 283\u2013289 (1999). https:\/\/doi.org\/10.1016\/S0020-0190(99)00025-3","journal-title":"Inf. Process. Lett."},{"key":"16_CR11","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of 3rd STOC, pp. 151\u2013158. ACM (1971). https:\/\/doi.org\/10.1145\/800157.805047","DOI":"10.1145\/800157.805047"},{"key":"16_CR12","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"4","key":"16_CR13","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 23:1\u201323:27 (2014). https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"key":"16_CR14","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. In: Monographs in Computer Science. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"16_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-662-43951-7_39","volume-title":"Automata, Languages, and Programming","author":"D Eisenstat","year":"2014","unstructured":"Eisenstat, D., Mathieu, C., Schabanel, N.: Facility location in evolving metrics. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 459\u2013470. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_39"},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976). https:\/\/doi.org\/10.1137\/0205048","journal-title":"SIAM J. Comput."},{"issue":"1","key":"16_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoret. Comput. Sci. 410(1), 53\u201361 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2008.09.065","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR18","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"16_CR19","doi-asserted-by":"publisher","unstructured":"Fluschnik, T., Niedermeier, R., Rohm, V., Zschoche, P.: Multistage vertex cover. In: Proceedings of 14th IPEC. LIPIcs, vol. 148, pp. 14:1\u201314:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.14","DOI":"10.4230\/LIPIcs.IPEC.2019.14"},{"key":"16_CR20","unstructured":"Fluschnik, T., Niedermeier, R., Schubert, C., Zschoche, P.: Multistage $$s$$-$$t$$ path: confronting similarity with dissimilarity. In: Proceedings of 31st ISAAC. LIPIcs, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020). Accepted for publication. https:\/\/arxiv.org\/abs\/2002.07569"},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011). https:\/\/doi.org\/10.1016\/j.jcss.2010.06.007","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-662-43948-7_47","volume-title":"Automata, Languages, and Programming","author":"A Gupta","year":"2014","unstructured":"Gupta, A., Talwar, K., Wieder, U.: Changing bases: multistage optimization for matroids and matchings. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 563\u2013575. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_47"},{"issue":"2","key":"16_CR23","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01896987","volume":"4","author":"P Hansen","year":"1987","unstructured":"Hansen, P., Jaumard, B.: Minimum sum of diameters clustering. J. Classif. 4(2), 215\u2013226 (1987). https:\/\/doi.org\/10.1007\/BF01896987","journal-title":"J. Classif."},{"key":"16_CR24","unstructured":"Heeger, K., Himmel, A., Kammer, F., Niedermeier, R., Renken, M., Sajenko, A.: Multistage problems on a global budget. CoRR abs\/1912.04392 (2019). http:\/\/arxiv.org\/abs\/1912.04392"},{"issue":"2","key":"16_CR25","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. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"16_CR26","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR27","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the Complexity of Computer Computations, held 20\u201322 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. The IBM Research Symposia Series. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"16_CR28","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/malq.19670130104","volume":"13","author":"MR Krom","year":"1967","unstructured":"Krom, M.R.: The decision problem for a class of first-order formulas in which all disjunctions are binary. Math. Logic Q. 13(1\u20132), 15\u201320 (1967). https:\/\/doi.org\/10.1002\/malq.19670130104","journal-title":"Math. Logic Q."},{"key":"16_CR29","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/92"},{"issue":"2","key":"16_CR30","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/0196-6774(86)90006-4","volume":"7","author":"R Raghavan","year":"1986","unstructured":"Raghavan, R., Cohoon, J., Sahni, S.: Single bend wiring. J. Algorithms 7(2), 232\u2013257 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90006-4","journal-title":"J. Algorithms"},{"issue":"2","key":"16_CR31","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0895480102396099","volume":"18","author":"S Ramnath","year":"2004","unstructured":"Ramnath, S.: Dynamic digraph connectivity hastens minimum sum-of-diameters clustering. SIAM J. Discrete Math. 18(2), 272\u2013286 (2004). https:\/\/doi.org\/10.1137\/S0895480102396099","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-75242-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:28:52Z","timestamp":1620142132000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 May 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 May 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic the conference was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}