{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:14:17Z","timestamp":1743023657867,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826962"},{"type":"electronic","value":"9783031826979"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-82697-9_11","type":"book-chapter","created":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:36Z","timestamp":1739614656000},"page":"142-156","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Roman Hitting Set"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0880-2513","authenticated-orcid":false,"given":"Kevin","family":"Mann","sequence":"first","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":[[2025,2,16]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Aazami, A., Cheriyan, J., Jampani, K.R.: Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs. Algorithmica 63(1-2), 425\u2013456 (2012)","DOI":"10.1007\/s00453-011-9540-3"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Bazgan, C., Chopin, M., Fernau, H.: Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences 82(3), 503\u2013520 (2016)","DOI":"10.1016\/j.jcss.2015.11.010"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Fernau, H., Mann, K.: Roman census: Enumerating and counting Roman dominating functions on graph classes. In: Leroux, J., Lombardy, S., Peleg, D. (eds.) 48th International Symposium on Mathematical Foundations of Computer Science, MFCS. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0272, pp. 6:1\u20136:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2023)","DOI":"10.2139\/ssrn.4557637"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F.N., Fernau, H., Mann, K.: Minimal Roman dominating functions: Extensions and enumeration. Algorithmica 86, 1862\u20131887 (2024)","DOI":"10.1007\/s00453-024-01211-w"},{"key":"11_CR5","unstructured":"Agarwal, U., Ramachandran, V.: Finding $$k$$ simple shortest paths and cycles. In: Hong, S. (ed.) 27th International Symposium on Algorithms and Computation, ISAAC. LIPIcs, vol.\u00a064, pp. 8:1\u20138:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Arquilla, J., Fredricksen, H.: \u201cGraphing\u201d an optimal grand strategy. Military Operations Research pp. 3\u201317 (Fall 1995), http:\/\/hdl.handle.net\/10945\/38438","DOI":"10.5711\/morj.1.3.3"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Kyropoulou, M.: An improved approximation bound for spanning star forest and color saving. In: Kr\u00e1lovic, R., Niwinski, D. (eds.) Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS. LNCS, vol.\u00a05734, pp. 90\u2013101. Springer (2009)","DOI":"10.1007\/978-3-642-03816-7_9"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Bermudo, S., Fernau, H.: Computing the differential of a graph: hardness, approximability and exact algorithms. Discrete Applied Mathematics 165, 69\u201382 (2014)","DOI":"10.1016\/j.dam.2012.11.013"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Bermudo, S., Fernau, H.: Combinatorics for smaller kernels: The differential of a graph. Theoretical Computer Science 562, 330\u2013345 (2015)","DOI":"10.1016\/j.tcs.2014.10.007"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Bermudo, S., Fernau, H., Sigarreta, J.M.: The differential and the Roman domination number of a graph. Applicable Analysis and Discrete Mathematics 8, 155\u2013171 (2014)","DOI":"10.2298\/AADM140210003B"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Casel, K., Fernau, H., Ghadikolaei, M.K., Monnot, J., Sikora, F.: On the complexity of solution extension of optimization problems. Theoretical Computer Science 904, 48\u201365 (2022)","DOI":"10.1016\/j.tcs.2021.10.017"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Chen, N., Engelberg, R., Nguyen, C.T., Raghavendra, P., Rudra, A., Singh, G.: Improved approximation algorithms for the spanning star forest problem. Algorithmica 65(3), 498\u2013516 (2013)","DOI":"10.1007\/s00453-011-9607-1"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Cockayne, E.J., Dreyer Jr., P., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Mathematics 278, 11\u201322 (2004)","DOI":"10.1016\/j.disc.2003.06.004"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Creignou, N., Kr\u00f6ll, M., Pichler, R., Skritek, S., Vollmer, H.: A complexity theory for hard enumeration problems. Discrete Applied Mathematics 268, 191\u2013209 (2019)","DOI":"10.1016\/j.dam.2019.02.025"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Dehne, F., Fellows, M., Fernau, H., Prieto, E., Rosamond, F.: Nonblocker: parameterized algorithmics for minimum dominating set. In: \u0160tuller, J., Wiedermann, J., Tel, G., Pokorn\u00fd, J., Bielikova, M. (eds.) Software Seminar SOFSEM. LNCS, vol.\u00a03831, pp. 237\u2013245. Springer (2006)","DOI":"10.1007\/11611257_21"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC. pp. 624\u2013633. ACM (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"11_CR19","unstructured":"Dreyer, P.A.: Applications and Variations of Domination in Graphs. Ph.D. thesis, Rutgers University, New Jersey, USA (2000)"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing 24(6), 1278\u20131304 (1995)","DOI":"10.1137\/S0097539793250299"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. Journal of the ACM 45, 634\u2013652 (1998)","DOI":"10.1145\/285055.285059"},{"key":"11_CR22","doi-asserted-by":"publisher","unstructured":"Fernau, H., Mann, K.: Hitting the Romans. Tech. Rep. abs\/2302.11417, ArXiv, Cornell University (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.11417","DOI":"10.48550\/arXiv.2302.11417"},{"key":"11_CR23","unstructured":"Fernau, H., Mann, K.: Perfect Roman domination and unique response Roman domination. Tech. rep., ArXiv, Cornell University (2023)"},{"key":"11_CR24","unstructured":"Fernau, H., Mann, K.: Roman hitting functions. In: Rz\u0105\u017cewski, P., Bonnet, E. (eds.) 19th International Symposium on Parameterized and Exact Computation, IPEC. LIPIcs, vol.\u00a0321, pp. 24:1\u201324:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"11_CR25","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms 5(1), 1\u201317 (2008)","DOI":"10.1145\/1435375.1435384"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"Gainer-Dewar, A., Vera-Licona, P.: The minimal hitting set generation problem: Algorithms and computation. SIAM Journal of Discrete Mathematics 31(1), 63\u2013100 (2017)","DOI":"10.1137\/15M1055024"},{"key":"11_CR28","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. New York: Freeman (1979)"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S., Henning, M.A. (eds.): Topics in Domination in Graphs, Developments in Mathematics, vol.\u00a064. Springer (2020)","DOI":"10.1007\/978-3-030-51117-3"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Jana, S., Modak, S., Saurabh, S., Singanporia, K.: Roman cycle hitting set. In: Kr\u00e1\u013e, D., Milani\u010d, M. (eds.) Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG. LNCS, vol. To appear. Springer (2024)","DOI":"10.1007\/978-3-031-75409-8_20"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM Journal of Discrete Mathematics 28(4), 1916\u20131929 (2014)","DOI":"10.1137\/120862612"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Li, K., Ran, Y., Zhang, Z., Du, D.: Nearly tight approximation algorithm for (connected) Roman dominating set. Optimization Letters 16(8), 2261\u20132276 (2022)","DOI":"10.1007\/s11590-022-01862-0"},{"key":"11_CR33","unstructured":"Mary, A., Strozecki, Y.: Efficient enumeration of solutions produced by closure operations. Discrete Mathematics & Theoretical Computer Science 21(3) (2019)"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Nguyen, C.T., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its application to genomic sequence alignment. SIAM Journal on Computing 38(3), 946\u2013962 (2008)","DOI":"10.1137\/070682150"},{"key":"11_CR35","doi-asserted-by":"crossref","unstructured":"Padamutham, C., Palagiri, V.S.R.: Algorithmic aspects of Roman domination in graphs. Journal of Applied Mathematics and Computing 64, 89\u2013102 (2020)","DOI":"10.1007\/s12190-020-01345-4"},{"key":"11_CR36","doi-asserted-by":"crossref","unstructured":"Pagourtzis, A., Penna, P., Schlude, K., Steinh\u00f6fel, K., Taylor, D.S., Widmayer, P.: Server placements, Roman domination and other dominating set variants. In: Baeza-Yates, R.A., Montanari, U., Santoro, N. (eds.) Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP 17$$^{\\text{th}}$$ World Computer Congress \u2014 TC1 Stream \/ 2$$^{\\text{ nd }}$$ IFIP International Conference on Theoretical Computer Science IFIP TCS. pp. 280\u2013291. Kluwer (2002), also available as Technical Report 365, ETH Z\u00fcrich, Institute of Theoretical Computer Science, 10\/2001.","DOI":"10.1007\/978-0-387-35608-2_24"},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 237\u2013252 (1975)","DOI":"10.1002\/net.1975.5.3.237"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Schwikowski, B., Speckenmeyer, E.: On enumerating all minimal solutions of feedback problems. Discrete Applied Mathematics 117, 253\u2013265 (2002)","DOI":"10.1016\/S0166-218X(00)00339-5"},{"key":"11_CR39","doi-asserted-by":"crossref","unstructured":"Stewart, I.: Defend the Roman Empire. Scientific American pp. 136,137,139 (Dec 1999)","DOI":"10.1038\/scientificamerican1299-136"},{"key":"11_CR40","unstructured":"Strozecki, Y.: Enumeration complexity. EATCS Bulletin 129 (2019)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82697-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:56Z","timestamp":1739614676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82697-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826962","9783031826979"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82697-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"16 February 2025","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 Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}