{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T01:00:48Z","timestamp":1740099648273,"version":"3.37.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030389185"},{"type":"electronic","value":"9783030389192"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-38919-2_20","type":"book-chapter","created":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T12:03:18Z","timestamp":1579176198000},"page":"236-247","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Dynamic Variants of Red-Blue Dominating Set"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5221-8421","authenticated-orcid":false,"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5460-6222","authenticated-orcid":false,"given":"Cristina","family":"Bazgan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,17]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.tcs.2015.06.053","volume":"607","author":"FN Abu-Khzam","year":"2015","unstructured":"Abu-Khzam, F.N., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: On the parameterized complexity of dynamic problems. Theoret. Comput. Sci. 607, 426\u2013434 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"20_CR2","unstructured":"Alman, J., Mnich, M., Williams, V.V.: Dynamic parameterized problems and algorithms. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP. LIPIcs, vol. 80, pp. 41:1\u201341:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Approximation and Online Algorithms","author":"D Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 201\u2013213. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-540-93980-1_16"},{"issue":"6","key":"20_CR4","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser, M.: Computing small partial coverings. Inf. Process. Lett. 85(6), 327\u2013331 (2003)","journal-title":"Inf. Process. Lett."},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H-J B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 50\u201365. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-77566-9_5"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-11269-0_4","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-hard. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 50\u201360. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-11269-0_4"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Cai, Z., Miao, D., Li, Y.: Deletion propagation for multiple key preserving conjunctive queries: approximations and complexity. In: International Conference on Data Engineering, ICDE, pp. 506\u2013517. IEEE (2019)","DOI":"10.1109\/ICDE.2019.00052"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M Cesati","year":"2003","unstructured":"Cesati, M.: The turing way to parameterized complexity. J. Comput. Syst. Sci. 67(4), 654\u2013685 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"20_CR9","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., et al.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41:1\u201341:24 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"20_CR10","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1007\/s10878-013-9629-5","volume":"29","author":"P Damaschke","year":"2015","unstructured":"Damaschke, P.: Parameterizations of hitting set of bundles and inverse scope. J. Comb. Optim. 29(4), 847\u2013858 (2015)","journal-title":"J. Comb. Optim."},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78\u201390. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-79723-4_9"},{"issue":"4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1109\/TST.2014.6867515","volume":"19","author":"RG Downey","year":"2014","unstructured":"Downey, R.G., Egan, J., Fellows, M.R., Rosamond, F.A., Shaw, P.: Dynamic dominating set and turbo-charging greedy heuristics. Tsinghua Sci. Technol. 19(4), 329\u2013337 (2014)","journal-title":"Tsinghua Sci. Technol."},{"issue":"1","key":"20_CR13","doi-asserted-by":"publisher","first-page":"70","DOI":"10.5614\/ejgta.2014.2.1.7","volume":"2","author":"H Fernau","year":"2014","unstructured":"Fernau, H., Rodr\u00edguez-Vel\u00e1zquez, J.A.: A survey on alliances and related parameters in graphs. Electron. J. Graph Theory Appl. 2(1), 70\u201386 (2014)","journal-title":"Electron. J. Graph Theory Appl."},{"issue":"1","key":"20_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-013-9844-6","volume":"72","author":"M Kao","year":"2015","unstructured":"Kao, M., Chen, H., Lee, D.: Capacitated domination: problem complexity and approximation algorithms. Algorithmica 72(1), 1\u201343 (2015)","journal-title":"Algorithmica"},{"key":"20_CR15","series-title":"ACM Distinguished Dissertations","volume-title":"Computational Complexity of Machine Learning","author":"MJ Kearns","year":"1990","unstructured":"Kearns, M.J.: Computational Complexity of Machine Learning. ACM Distinguished Dissertations. MIT Press, Cambridge (1990)"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Khuller, S., Purohit, M., Sarpatwar, K.K.: Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems. In: Symposium on Discrete Algorithms (SODA), pp. 1702\u20131713. SIAM (2014)","DOI":"10.1137\/1.9781611973402.123"},{"issue":"3","key":"20_CR17","doi-asserted-by":"publisher","first-page":"31:1","DOI":"10.1145\/2885499","volume":"12","author":"I Koutis","year":"2016","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. ACM Trans. Algorithms 12(3), 31:1\u201331:18 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"20_CR18","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Lin, B.: The parameterized complexity of k-biclique. In: Symposium on Discrete Algorithms (SODA), pp. 605\u2013615. SIAM (2015)","DOI":"10.1137\/1.9781611973730.41"},{"issue":"5","key":"20_CR20","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"Lin, B.: The parameterized complexity of the k-biclique problem. J. ACM 65(5), 34:1\u201334:23 (2018)","journal-title":"J. ACM"},{"issue":"6","key":"20_CR21","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s10559-010-9269-z","volume":"46","author":"VA Mikhailyuk","year":"2010","unstructured":"Mikhailyuk, V.A.: Reoptimization of set covering problems. Cybern. Syst. Anal. 46(6), 879\u2013883 (2010)","journal-title":"Cybern. Syst. Anal."},{"issue":"2","key":"20_CR22","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648\u2013670 (1999)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2020: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-38919-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T12:13:05Z","timestamp":1579176785000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-38919-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030389185","9783030389192"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-38919-2_20","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":"17 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Limassol","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 January 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"46","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cyprusconferences.org\/sofsem2020\/","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":"125","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":"40","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":"17","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":"32% - 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":"2.9","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":"3.8","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)"}}]}}