{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T10:21:04Z","timestamp":1751192464496,"version":"3.40.3"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031630200"},{"type":"electronic","value":"9783031630217"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_27","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:02:29Z","timestamp":1718974949000},"page":"354-368","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Perfect Roman Domination: Aspects of\u00a0Enumeration and\u00a0Parameterization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0880-2513","authenticated-orcid":false,"given":"Kevin","family":"Mann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2017.06.014","volume":"232","author":"H Abdollahzadeh Ahangar","year":"2017","unstructured":"Abdollahzadeh Ahangar, H., Chellali, M., Sheikholeslami, S.M.: On the double Roman domination in graphs. Discret. Appl. Math. 232, 1\u20137 (2017)","journal-title":"Discret. Appl. Math."},{"key":"27_CR2","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-031-15914-5_1","volume-title":"Graph-Theoretic Concepts in Computer Science - WG 2022","author":"FN Abu-Khzam","year":"2022","unstructured":"Abu-Khzam, F.N., Fernau, H., Mann, K.: Minimal Roman dominating functions: extensions and enumeration. In: Bekos, M.A., Kaufmann, M. (eds.) WG 2022. LNCS, vol. 13453, pp. 1\u201315. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_1"},{"key":"27_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. Technical report, 2208.05261, Cornell University, arXiv\/CoRR (2022). https:\/\/arxiv.org\/abs\/2208.05261","DOI":"10.2139\/ssrn.4557637"},{"key":"27_CR4","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":"27_CR5","doi-asserted-by":"publisher","first-page":"3889","DOI":"10.1007\/s00453-023-01171-7","volume":"85","author":"S Banerjee","year":"2023","unstructured":"Banerjee, S., Chaudhary, J., Pradhan, D.: Unique response Roman domination: complexity and algorithms. Algorithmica 85, 3889\u20133927 (2023). https:\/\/doi.org\/10.1007\/s00453-023-01171-7","journal-title":"Algorithmica"},{"issue":"1","key":"27_CR6","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s10878-019-00457-3","volume":"39","author":"S Banerjee","year":"2020","unstructured":"Banerjee, S., Henning, M.A., Pradhan, D.: Algorithmic results on double Roman domination in graphs. J. Comb. Optim. 39(1), 90\u2013114 (2020)","journal-title":"J. Comb. Optim."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.08.017","volume":"796","author":"S Banerjee","year":"2019","unstructured":"Banerjee, S., Keil, J.M., Pradhan, D.: Perfect Roman domination in graphs. Theoret. Comput. Sci. 796, 1\u201321 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2016.03.017","volume":"211","author":"RA Beeler","year":"2016","unstructured":"Beeler, R.A., Haynes, T.W., Hedetniemi, S.T.: Double Roman domination. Discret. Appl. Math. 211, 23\u201329 (2016)","journal-title":"Discret. Appl. Math."},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Cabrera\u00a0Mart\u00ednez, A., Puertas, M., Rodr\u00edguez-Vel\u00e1zquez, J.: On the 2-packing differential of a graph. Results Math. 76, 175:1\u2013175:24 (2021)","DOI":"10.1007\/s00025-021-01473-8"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R., Fellows, M.: On the parameterized complexity of short computation and factorization. Arch. Math. Logic 36, 321\u2013337 (1997)","journal-title":"Arch. Math. Logic"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-319-06089-7_7","volume-title":"Theory and Applications of Models of Computation","author":"D Cattan\u00e9o","year":"2014","unstructured":"Cattan\u00e9o, D., Perdrix, S.: The parameterized\u00a0complexity of domination-type problems and application\u00a0to\u00a0linear\u00a0codes. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 86\u2013103. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-06089-7_7"},{"key":"27_CR12","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, 654\u2013685 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"27_CR13","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00373-015-1566-x","volume":"32","author":"M Chellali","year":"2016","unstructured":"Chellali, M., Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., McRae, A.A.: A Roman domination chain. Graphs Combin. 32(1), 79\u201392 (2016)","journal-title":"Graphs Combin."},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.dam.2015.11.013","volume":"204","author":"M Chellali","year":"2016","unstructured":"Chellali, M., Haynes, T.W., Hedetniemi, S.T., McRae, A.A.: Roman {2}-domination. Discret. Appl. Math. 204, 22\u201328 (2016)","journal-title":"Discret. Appl. Math."},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne, E.J., Dreyer, P., Jr., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discret. Math. 278, 11\u201322 (2004)","journal-title":"Discret. Math."},{"issue":"2","key":"27_CR16","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"27_CR18","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"27_CR19","unstructured":"Dreyer, P.A.: Applications and variations of domination in graphs. Ph.D. thesis, Rutgers University, New Jersey, USA (2000)"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1080\/00207160701374376","volume":"85","author":"H Fernau","year":"2008","unstructured":"Fernau, H.: Roman domination: a parameterized perspective. Int. J. Comput. Math. 85, 25\u201338 (2008)","journal-title":"Int. J. Comput. Math."},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-319-78825-8_3","volume-title":"Combinatorial Algorithms","author":"H Fernau","year":"2018","unstructured":"Fernau, H.: Extremal kernelization: a commemorative paper. In: Brankovic, L., Ryan, J., Smyth, W.F. (eds.) IWOCA 2017. LNCS, vol. 10765, pp. 24\u201336. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78825-8_3"},{"issue":"10","key":"27_CR22","first-page":"63","volume":"8","author":"H Fernau","year":"2018","unstructured":"Fernau, H., Golovach, P.A., Sagot, M.: Algorithmic enumeration: output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Rep. 8(10), 63\u201386 (2018)","journal-title":"Dagstuhl Rep."},{"key":"27_CR23","unstructured":"Fernau, H., Mann, K.: Parameterized complexity aspects of extension problems (2024). Unpublished manuscript; parts are contained in [?]"},{"key":"27_CR24","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. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"27_CR25","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Interval graphs. In: Annals of Discrete Mathematics, vol.\u00a057, chap.\u00a08, pp. 171\u2013202. Elsevier (2004)","DOI":"10.1016\/S0167-5060(04)80056-6"},{"issue":"3","key":"27_CR26","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"27_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"J Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Downey, R., Fellows, M., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 162\u2013173. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28639-4_15"},{"key":"27_CR28","series-title":"Developments in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58892-2","volume-title":"Structures of Domination in Graphs","author":"TW Haynes","year":"2021","unstructured":"Haynes, T.W., Hedetniemi, S.T., Henning, M.A.: Structures of Domination in Graphs. Developments in Mathematics, vol. 66. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-58892-2"},{"key":"27_CR29","series-title":"Developments in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51117-3","volume-title":"Topics in Domination in Graphs","year":"2020","unstructured":"Haynes, T.W., Hedetniemi, S., Henning, M.A. (eds.): Topics in Domination in Graphs. Developments in Mathematics, vol. 64. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51117-3"},{"key":"27_CR30","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.dam.2017.10.027","volume":"236","author":"MA Henning","year":"2018","unstructured":"Henning, M.A., Klostermeyer, W.F., MacGillivray, G.: Perfect Roman domination in trees. Discret. Appl. Math. 236, 235\u2013245 (2018)","journal-title":"Discret. Appl. Math."},{"key":"27_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6525-6","volume-title":"Total Domination in Graphs","author":"M Hennings","year":"2013","unstructured":"Hennings, M., Yeo, A.: Total Domination in Graphs. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-6525-6"},{"key":"27_CR32","doi-asserted-by":"publisher","first-page":"3444","DOI":"10.1016\/j.disc.2012.02.005","volume":"312","author":"K Junosza-Szaniawski","year":"2012","unstructured":"Junosza-Szaniawski, K., Rz\u0105\u017cewski, P.: On the number of 2-packings in a connected graph. Discret. Math. 312, 3444\u20133450 (2012)","journal-title":"Discret. Math."},{"key":"27_CR33","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BFb0017162","volume-title":"Mathematical Foundations of Computer Science 1988","author":"J Kratochv\u00edl","year":"1988","unstructured":"Kratochv\u00edl, J., K\u0159iv\u00e1nek, M.: On the computational complexity of codes in graphs. In: Chytil, M., Janiga, L., Koubek, V. (eds.) MFCS 1988. LNCS, vol. 324, pp. 396\u2013404. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFb0017162"},{"issue":"18","key":"27_CR34","doi-asserted-by":"publisher","first-page":"3400","DOI":"10.1016\/j.dam.2008.01.011","volume":"156","author":"M Liedloff","year":"2008","unstructured":"Liedloff, M., Kloks, T., Liu, J., Peng, S.L.: Efficient algorithms for Roman domination on some classes of graphs. Discret. Appl. Math. 156(18), 3400\u20133415 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"27_CR35","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s10878-012-9482-y","volume":"26","author":"CH Liu","year":"2013","unstructured":"Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. J. Comb. Optim. 26(3), 608\u2013619 (2013)","journal-title":"J. Comb. Optim."},{"issue":"1\u20133","key":"27_CR36","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0166-218X(01)00184-6","volume":"117","author":"CL Lu","year":"2002","unstructured":"Lu, C.L., Tang, C.Y.: Weighted efficient domination problem on some perfect graphs. Discret. Appl. Math. 117(1\u20133), 163\u2013182 (2002)","journal-title":"Discret. Appl. Math."},{"key":"27_CR37","doi-asserted-by":"crossref","unstructured":"Marino, A.: Analysis and enumeration. Algorithms for biological graphs, Atlantis Studies in Computing, vol.\u00a06. Atlantis Press, Paris (2015)","DOI":"10.2991\/978-94-6239-097-3"},{"key":"27_CR38","unstructured":"Peng, S.L., Tsai, Y.H.: Roman domination on graphs of bounded treewidth. In: The 24th Workshop on Combinatorial Mathematics and Computation Theory, pp. 128\u2013131 (2007)"},{"issue":"24","key":"27_CR39","doi-asserted-by":"publisher","first-page":"3194","DOI":"10.1016\/j.disc.2007.03.020","volume":"307","author":"RR Rubalcaba","year":"2007","unstructured":"Rubalcaba, R.R., Slater, P.J.: Roman dominating influence parameters. Discret. Math. 307(24), 3194\u20133200 (2007)","journal-title":"Discret. Math."},{"issue":"1","key":"27_CR40","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1142\/S1793830910000504","volume":"2","author":"W Shang","year":"2010","unstructured":"Shang, W., Wang, X., Hu, X.: Roman domination and its variants in unit disk graphs. Discrete Math. Algorithms Appl. 2(1), 99\u2013106 (2010)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"27_CR41","doi-asserted-by":"crossref","unstructured":"Stewart, I.: Defend the Roman Empire. Scientific American, pp. 136, 137, 139 (1999)","DOI":"10.1038\/scientificamerican1299-136"},{"key":"27_CR42","unstructured":"Strozecki, Y.: Enumeration complexity. EATCS Bull. 129 (2019)"},{"issue":"11","key":"27_CR43","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1016\/j.dam.2011.03.013","volume":"159","author":"EE Targhi","year":"2011","unstructured":"Targhi, E.E., Rad, N.J., Volkmann, L.: Unique response Roman domination in graphs. Discret. Appl. Math. 159(11), 1110\u20131117 (2011)","journal-title":"Discret. Appl. Math."},{"key":"27_CR44","unstructured":"Wasa, K.: Enumeration of enumeration algorithms. Technical report, 1605.05102, Archiv, Cornell University (2016)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T13:16:06Z","timestamp":1718975766000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}