{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:35:45Z","timestamp":1743068145821,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030752415"},{"type":"electronic","value":"9783030752422"}],"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_1","type":"book-chapter","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:22:29Z","timestamp":1620141749000},"page":"3-19","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Invited Talks"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katharina T.","family":"Huber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-319-29221-2_6","volume-title":"Algorithms and Discrete Applied Mathematics","author":"C Bazgan","year":"2016","unstructured":"Bazgan, C., Brankovic, L., Casel, K., Fernau, H.: On the complexity landscape of the domination chain. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 61\u201372. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29221-2_6"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan, C., et al.: The many facets of upper domination. Theoret. Comput. Sci. 717, 2\u201325 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"1_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M Bir\u00f3","year":"1992","unstructured":"Bir\u00f3, M., Hujter, M., Tuza, Z.: Precoloring extension. I. Interval graphs. Discrete Math. 100(1\u20133), 267\u2013279 (1992)","journal-title":"Discrete Math."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/3-540-48224-5_8","volume-title":"Automata, Languages and Programming","author":"E Boros","year":"2001","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: On generating all minimal integer solutions for a monotone system of linear inequalities. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 92\u2013103. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_8"},{"issue":"2","key":"1_CR6","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E Boros","year":"1998","unstructured":"Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive Boolean functions. Optim. Methods Softw. 10(2), 147\u2013156 (1998)","journal-title":"Optim. Methods Softw."},{"issue":"6","key":"1_CR7","doi-asserted-by":"publisher","first-page":"2036","DOI":"10.1137\/S0097539700370072","volume":"30","author":"E Boros","year":"2000","unstructured":"Boros, E., Gurvich, V., Khachiyan, L., Makino, K.: Dual-bounded generating problems: partial and multiple transversals of a hypergraph. SIAM J. Comput. 30(6), 2036\u20132050 (2000)","journal-title":"SIAM J. Comput."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.003","volume":"511","author":"L Brankovic","year":"2013","unstructured":"Brankovic, L., Fernau, H.: A novel parameterised approximation algorithm for minimum vertex cover. Theoret. Comput. Sci. 511, 85\u2013108 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-030-59267-7_30","volume-title":"Theory and Applications of Models of Computation","author":"J Bruchertseifer","year":"2020","unstructured":"Bruchertseifer, J., Fernau, H.: Synchronizing words and monoid factorization: a parameterized perspective. In: Chen, J., Feng, Q., Xu, J. (eds.) TAMC 2020. LNCS, vol. 12337, pp. 352\u2013364. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59267-7_30"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-030-25027-0_13","volume-title":"Fundamentals of Computation Theory","author":"K Casel","year":"2019","unstructured":"Casel, K., Fernau, H., Khosravian Ghadikolaei, M., Monnot, J., Sikora, F.: Extension of some edge graph problems: standard and parameterized complexity. In: G\u0105sieniec, L.A., Jansson, J., Levcopoulos, C. (eds.) FCT 2019. LNCS, vol. 11651, pp. 185\u2013200. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-25027-0_13"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-030-17402-6_11","volume-title":"Algorithms and Complexity","author":"K Casel","year":"2019","unstructured":"Casel, K., Fernau, H., Ghadikoalei, M.K., Monnot, J., Sikora, F.: Extension of vertex cover and independent set in some classes of graphs. In: Heggernes, P. (ed.) CIAC 2019. LNCS, vol. 11485, pp. 124\u2013136. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17402-6_11"},{"key":"1_CR12","unstructured":"K. Casel, H. Fernau, M. Khosravian G., J. Monnot, and F. Sikora. On the complexity of solution extension of optimization problems. Manuscript submitted to Theoretical Computer Science (2020)"},{"issue":"3","key":"1_CR13","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.tcs.2006.07.016","volume":"363","author":"J Chen","year":"2006","unstructured":"Chen, J., Zhang, F.: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]. Theoret. Comput. Sci. 363(3), 278\u2013288 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/978-3-319-21275-3_15","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Lower bounds for kernelization. Parameterized Algorithms, pp. 523\u2013555. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3_15"},{"issue":"3","key":"1_CR15","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theoret. Comput. Sci. 351(3), 337\u2013350 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.jcss.2017.11.001","volume":"93","author":"MR Fellows","year":"2018","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F.A., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. J. Comput. Syst. Sci. 93, 30\u201340 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/3-540-45655-4_60","volume-title":"Computing and Combinatorics","author":"H Fernau","year":"2002","unstructured":"Fernau, H.: On parameterized enumeration. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol. 2387, pp. 564\u2013573. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45655-4_60"},{"key":"1_CR18","first-page":"287","volume":"24","author":"H Fernau","year":"2019","unstructured":"Fernau, H., Hoffmann, S.: Extensions to minimal synchronizing words. J. Automata Lang. Comb. 24, 287\u2013307 (2019)","journal-title":"J. Automata Lang. Comb."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.dam.2014.12.010","volume":"199","author":"PA Golovach","year":"2016","unstructured":"Golovach, P.A., Heggernes, P., Kant\u00e9, M.M., Kratsch, D., Villanger, Y.: Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Appl. Math. 199, 30\u201336 (2016)","journal-title":"Discrete Appl. Math."},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.dam.2016.01.038","volume":"216","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Heggernes, P., Kant\u00e9, M.M., Kratsch, D., Villanger, Y.: Minimal dominating sets in interval graphs and trees. Discrete Appl. Math. 216, 162\u2013170 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1_CR21","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1007\/s00453-014-9875-7","volume":"72","author":"PA Golovach","year":"2015","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Villanger, Y.: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica 72(3), 836\u2013859 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"1_CR22","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1_CR23","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"MM Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28(4), 1916\u20131929 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-319-21840-3_37","volume-title":"Algorithms and Data Structures","author":"MM Kant\u00e9","year":"2015","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 446\u2013457. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_37"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-662-53174-7_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MM Kant\u00e9","year":"2016","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 138\u2013153. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53174-7_11"},{"issue":"1","key":"1_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00453-007-9074-x","volume":"50","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: On enumerating minimal dicuts and strongly connected subgraphs. Algorithmica 50(1), 159\u2013172 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"1_CR27","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"LG Khachiyan","year":"2005","unstructured":"Khachiyan, L.G., Boros, E., Elbassioni, K.M., Gurvich, V., Makino, K.: On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math. 19(4), 966\u2013984 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR28","unstructured":"Khosravian Ghadikolaei, M.: Extension of NP Optimization Problems. Ph.D. thesis, Universit\u00e9 Paris Dauphine, France, July 2019"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-030-25005-8_26","volume-title":"Combinatorial Algorithms","author":"M Khosravian Ghadikoalei","year":"2019","unstructured":"Khosravian Ghadikoalei, M., Melissinos, N., Monnot, J., Pagourtzis, A.: Extension and its price for the connected vertex cover problem. In: Colbourn, C.J., Grossi, R., Pisanti, N. (eds.) IWOCA 2019. LNCS, vol. 11638, pp. 315\u2013326. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-25005-8_26"},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"EL Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"key":"1_CR31","unstructured":"Manlove, D.F.: Minimaximal and maximinimal optimisation problems: a partial order-based approach. Ph.D. thesis, University of Glasgow, Computing Science (1998)"},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"Marx, D.: NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory 49(4), 313\u2013324 (2005)","DOI":"10.1002\/jgt.20085"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"1_CR34","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0166-218X(00)00339-5","volume":"117","author":"B Schwikowski","year":"2002","unstructured":"Schwikowski, B., Speckenmeyer, E.: On enumerating all minimal solutions of feedback problems. Discrete Appl. Math. 117, 253\u2013265 (2002)","journal-title":"Discrete Appl. Math."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Sipser, M.: The history and status of the P versus NP question. In: Kosaraju, S.R., Fellows, M., Wigderson, M.A., Ellis, J.A. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC, pp. 603\u2013618. ACM (1992)","DOI":"10.1145\/129712.129771"}],"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_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T15:24:03Z","timestamp":1620141843000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-75242-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030752415","9783030752422"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-75242-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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)"}}]}}