{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:33Z","timestamp":1740122373715,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Chongqing Natural Science Foundation Innovation and Development Joint Fund","award":["CSTB2022NSCQ- LZX0003"],"award-info":[{"award-number":["CSTB2022NSCQ- LZX0003"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701059"],"award-info":[{"award-number":["11701059"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Youth project of science and technology research program of Chongqing Education Commission of China","award":["KJQN202101130"],"award-info":[{"award-number":["KJQN202101130"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s10878-024-01206-x","type":"journal-article","created":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T17:01:38Z","timestamp":1728147698000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The k-th Roman domination problem is polynomial on interval graphs"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3092-9692","authenticated-orcid":false,"given":"Peng","family":"Li","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,5]]},"reference":[{"key":"1206_CR1","first-page":"126662","volume":"414","author":"HA Ahangar","year":"2022","unstructured":"Ahangar HA, Chellali M, Sheikholeslami SM, Valenzuela-Tripodoro JC (2022) Maximal double Roman domination in graphs. Appl Math Comput 414:126662","journal-title":"Appl Math Comput"},{"key":"1206_CR2","first-page":"125444","volume":"391","author":"HA Ahangar","year":"2021","unstructured":"Ahangar HA, Alvarez MP, Chellali M, Sheikholeslami SM, Valenzuela-Tripodoro JC (2021) Triple Roman domination in graphs. Appl Math Comput 391:125444","journal-title":"Appl Math Comput"},{"key":"1206_CR3","first-page":"124617","volume":"364","author":"H Abdollahzadeh Ahangar","year":"2020","unstructured":"Abdollahzadeh Ahangar H, Chellali M, Sheikholeslami SM (2020) Outer independent double Roman domination. Appl Math Comput 364:124617","journal-title":"Appl Math Comput"},{"issue":"7","key":"1206_CR4","doi-asserted-by":"publisher","first-page":"2250125","DOI":"10.1142\/S179355712250125X","volume":"15","author":"J Amjadi","year":"2022","unstructured":"Amjadi J, Sadeghi H (2022) Double Roman domination subdivision number in graphs. Asian-Eur J Math 15(7):2250125","journal-title":"Asian-Eur J Math"},{"key":"1206_CR5","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 Michael A, Pradhan D (2020) Algorithmic results on double Roman domination in graphs. J Combinatorial Optim 39:90\u2013114","journal-title":"J Combinatorial Optim"},{"key":"1206_CR6","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2016.03.017","volume":"211","author":"RA Beeler","year":"2016","unstructured":"Beeler RA, Haynes TW, Hedetniemi ST (2016) Double Roman domination. Discret Appl Math 211:23\u201329","journal-title":"Discret Appl Math"},{"key":"1206_CR7","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-030-58892-2_10","volume-title":"Structures of domination in graphs","author":"M Chellali","year":"2021","unstructured":"Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2021) Varieties of Roman domination. In: Haynes TW, Hedetniemi ST, Henning MA (eds) Structures of domination in graphs. Springer, Berlin\/Heidelberg, pp 273\u2013307"},{"key":"1206_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/978-3-030-51117-3_11","volume-title":"Topics in domination in graphs","author":"M Chellali","year":"2020","unstructured":"Chellali M, Jafari Rad N, Sheikholeslami SM, Volkmann L (2020) Roman domination in graphs. In: Haynes TW, Hedetniemi ST, Henning MA (eds) Topics in domination in graphs. Springer, Berlin\/Heidelberg, pp 365\u2013409"},{"key":"1206_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"EJ Cockayne","year":"2004","unstructured":"Cockayne EJ, Dreyer PM Sr, Hedetniemi SM, Hedetniemi ST (2004) Roman domination in graphs. Discrete mathematics 278:11\u201322","journal-title":"Discrete mathematics"},{"doi-asserted-by":"crossref","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs, 2nd ed., Annals of Discrete Mathematics, 57, Elsevier, Amsterdam, The Netherlands","key":"1206_CR10","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"1206_CR11","volume-title":"Domination in graphs: advanced topics","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: advanced topics. Marcel Dekker Inc, New York"},{"key":"1206_CR12","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of domination in graphs. Marcel Dekker Inc, New York"},{"key":"1206_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"MA Henning","year":"2003","unstructured":"Henning MA, Hedetniemi ST (2003) Defending the Roman empire-A new strategy. Discrete mathematics 266:239\u2013251","journal-title":"Discrete mathematics"},{"issue":"2","key":"1206_CR14","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.tcs.2015.03.012","volume":"16","author":"P Li","year":"2015","unstructured":"Li P, Wu Y (2015) Spanning connectedness and Hamiltonian thickness of graphs and interval graphs. Discrete mathematics & theoretical computer science 16(2):125\u2013210","journal-title":"Discrete mathematics & theoretical computer science"},{"issue":"1","key":"1206_CR15","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/140981265","volume":"31","author":"P Li","year":"2017","unstructured":"Li P, Wu Y (2017) A linear time algorithm for the 1-Fixed-Endpoint path cover problem on interval graphs. SIAM J Discret Math 31(1):210\u2013239","journal-title":"SIAM J Discret Math"},{"key":"1206_CR16","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 (2008) Efficient algorithms for Roman domination on some classes of graphs. Discret Appl Math 156:3400\u20133415","journal-title":"Discret Appl Math"},{"key":"1206_CR17","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/080733085","volume":"26","author":"CH Liu","year":"2012","unstructured":"Liu CH, Chang GJ (2012) Roman domination on 2-connected graphs. SIAM J Discret Math 26:193\u2013205","journal-title":"SIAM J Discret Math"},{"key":"1206_CR18","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s10878-012-9482-y","volume":"26","author":"CH Liu","year":"2013","unstructured":"Liu CH, Chang GJ (2013) Roman domination on strongly chordal graphs. J Combinatorial Optim 26:608\u2013619","journal-title":"J Combinatorial Optim"},{"key":"1206_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.08.020","author":"D Pradhan","year":"2021","unstructured":"Pradhan D, Banerjee S, Jia-Bao L (2021) Perfect Italian domination in graphs: complexity and algorithms. Discret Appl Math. https:\/\/doi.org\/10.1016\/j.dam.2021.08.020","journal-title":"Discret Appl Math"},{"key":"1206_CR20","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.dam.2020.06.023","volume":"285","author":"A Poureidi","year":"2020","unstructured":"Poureidi A, Rad NJ (2020) Algorithmic complexity of double Roman graphs. Discret Appl Math 285:539\u2013551","journal-title":"Discret Appl Math"},{"key":"1206_CR21","first-page":"235","volume":"59","author":"A Raychaudhuri","year":"1987","unstructured":"Raychaudhuri A (1987) On powers of interval and unit interval graphs. Congressus Numerantium 59:235\u2013242","journal-title":"Congressus Numerantium"},{"key":"1206_CR22","first-page":"40","volume":"49","author":"CS Revelle","year":"1997","unstructured":"Revelle CS (1997) Can you protect the Roman empire? Johns Hopkins Mag 49:40\u201343","journal-title":"Johns Hopkins Mag"},{"key":"1206_CR23","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2021.01.005","volume":"859","author":"J Shang","year":"2021","unstructured":"Shang J, Li P, Shi Y (2021) The longest cycle problem is polynomial on interval graphs. Theor Comput Sci 859:37\u201347","journal-title":"Theor Comput Sci"},{"key":"1206_CR24","first-page":"237","volume":"241","author":"WT Trotter","year":"1997","unstructured":"Trotter WT (1997) New perspectives on interval orders and interval graphs. Surv Combinatorics 241:237\u2013286","journal-title":"Surv Combinatorics"},{"key":"1206_CR25","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/s10878-021-00735-z","volume":"42","author":"C-X Wang","year":"2021","unstructured":"Wang C-X, Yang Y, Wang H-J, Xu S-J (2021) Roman $$\\{k\\}$$-domination in trees and complexity results for some classes of graphs. J Combinatorial Optim 42:174\u2013186","journal-title":"J Combinatorial Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01206-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01206-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01206-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T19:09:42Z","timestamp":1729192182000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01206-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1206"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01206-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"26 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"17"}}