{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T21:39:19Z","timestamp":1785274759838,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642452772","type":"print"},{"value":"9783642452789","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45278-9_8","type":"book-chapter","created":{"date-parts":[[2013,11,25]],"date-time":"2013-11-25T15:35:18Z","timestamp":1385393718000},"page":"81-93","source":"Crossref","is-referenced-by-count":4,"title":["Exact Algorithms for Weak Roman Domination"],"prefix":"10.1007","author":[{"given":"Mathieu","family":"Chapelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred","family":"Cochefert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Fran\u00e7ois","family":"Couturier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Perez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1137\/070699688","volume":"23","author":"E.W. Chambers","year":"2009","unstructured":"Chambers, E.W., Kinnersley, B., Prince, N., West, D.B.: Extremal problems for roman domination. SIAM J. Discret. Math.\u00a023(3), 1575\u20131586 (2009)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"8_CR2","first-page":"195","volume":"9","author":"M. Chellali","year":"2012","unstructured":"Chellali, M., Rad, N.J., Volkmann, L.: Some results on roman domination edge critical graphs. AKCE Int. J. Graphs Comb.\u00a09(2), 195\u2013203 (2012)","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"8_CR3","first-page":"87","volume":"39","author":"E.J. Cockayne","year":"2003","unstructured":"Cockayne, E.J., Favaron, O., Mynhardt, C.M.: Secure domination, weak roman domination and forbidden subgraphs. Bull. Inst. Combin. Appl.\u00a039, 87\u2013100 (2003)","journal-title":"Bull. Inst. Combin. Appl."},{"key":"8_CR4","first-page":"19","volume":"67","author":"E.J. Cockayne","year":"2005","unstructured":"Cockayne, E.J., Grobler, P.J.P., Gr\u00fcndlingh, W.R., Munganga, J., van Vuuren, J.H.: Protection of a graph. Util. Math.\u00a067, 19\u201332 (2005)","journal-title":"Util. Math."},{"issue":"1-3","key":"8_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.disc.2003.06.004","volume":"278","author":"E.J. Cockayne","year":"2004","unstructured":"Cockayne, E.J., Dreyer Jr., P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discret. Math.\u00a0278(1-3), 11\u201322 (2004)","journal-title":"Discret. Math."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"3447","DOI":"10.1016\/j.disc.2008.09.043","volume":"309","author":"O. Favaron","year":"2009","unstructured":"Favaron, O., Karami, K., Khoeilar, R., Sheikholeslami, S.M.: On the roman domination number of a graph. Discret. Math.\u00a0309, 3447\u20133451 (2009)","journal-title":"Discret. Math."},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM\u00a056(5) (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"8_CR8","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman (1979)"},{"key":"8_CR9","first-page":"160","volume":"52","author":"W. Goddard","year":"2005","unstructured":"Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T.: Eternal security in graphs. J. Combin. Math. Combin. Comput.\u00a052, 160\u2013180 (2005)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"2589","DOI":"10.1016\/j.disc.2007.06.005","volume":"308","author":"J.L. Goldwasser","year":"2008","unstructured":"Goldwasser, J.L., Klostermeyer, W.F.: Tight bounds for eternal dominating sets in graphs. Discret. Math.\u00a0308, 2589\u20132593 (2008)","journal-title":"Discret. Math."},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"5820","DOI":"10.1016\/j.disc.2008.05.050","volume":"309","author":"P.J.P. Grobler","year":"2009","unstructured":"Grobler, P.J.P., Mynhardt, C.M.: Secure domination critical graphs. Discret. Math.\u00a0309, 5820\u20135827 (2009)","journal-title":"Discret. Math."},{"key":"8_CR12","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs: advanced topics. Pure and Applied Mathematics, vol.\u00a0209. Marcel Dekker Inc. (1998)"},{"issue":"1-3","key":"8_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0012-365X(02)00811-7","volume":"266","author":"M.A. Henning","year":"2003","unstructured":"Henning, M.A., Hedetniemi, S.T.: Defending the Roman Empire: a new strategy. Discret. Math.\u00a0266(1-3), 239\u2013251 (2003)","journal-title":"Discret. Math."},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-28050-4_4","volume-title":"Parameterized and Exact Computation","author":"Y. Iwata","year":"2012","unstructured":"Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 41\u201354. Springer, Heidelberg (2012)"},{"key":"8_CR15","unstructured":"Liedloff, M.: Algorithmes exacts et exponentiels pour les probl\u00e8mes NP-difficiles: domination, variantes et g\u00e9n\u00e9ralisations. Phd thesis, Laboratoire d\u2019Informatique Th\u00e9orique et Appliqu\u00e9e, Universit\u00e9 Paul Verlaine, Metz (2007)"},{"issue":"5","key":"8_CR16","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ipl.2008.02.009","volume":"107","author":"M. Liedloff","year":"2008","unstructured":"Liedloff, M.: Finding a dominating set on bipartite graphs. Inf. Proc. Lett.\u00a0107(5), 154\u2013157 (2008)","journal-title":"Inf. Proc. Lett."},{"key":"8_CR17","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. App. Math.\u00a0156, 3400\u20133415 (2008)","journal-title":"Discret. App. Math."},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/080733085","volume":"26","author":"C.-H. Liu","year":"2012","unstructured":"Liu, C.-H., Chang, G.J.: Roman domination on 2-connected graphs. SIAM J. Discret. Math.\u00a026(1), 193\u2013205 (2012)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"8_CR19","doi-asserted-by":"publisher","first-page":"161","DOI":"10.7151\/dmgt.1532","volume":"31","author":"T.N.M. Malini Mai","year":"2011","unstructured":"Malini Mai, T.N.M., Roushini Leely Pushpam, P.: Weak roman domination in graphs. Discussiones Mathematicae Graph Theory\u00a031(1), 161\u2013170 (2011)","journal-title":"Discussiones Mathematicae Graph Theory"},{"issue":"7","key":"8_CR20","doi-asserted-by":"publisher","first-page":"585","DOI":"10.2307\/2589113","volume":"107","author":"C.S. ReVelle","year":"2000","unstructured":"ReVelle, C.S., Rosing, K.E.: Defendens Imperium Romanum: a classical problem in military strategy. Math. Assoc. of America\u00a0107(7), 585\u2013594 (2000)","journal-title":"Math. Assoc. of America"},{"issue":"6","key":"8_CR21","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1038\/scientificamerican1299-136","volume":"281","author":"I. Stewart","year":"1999","unstructured":"Stewart, I.: Defend the Roman Empire!. Scientific American\u00a0281(6), 136\u2013139 (1999)","journal-title":"Scientific American"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M.: Exact exponential-time algorithms for domination problems in graphs. Phd thesis, Utrecht University, Netherlands (2011)","DOI":"10.1007\/s00453-011-9546-x"},{"issue":"17","key":"8_CR23","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"J.M.M. Rooij van","year":"2011","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discret. App. Math.\u00a0159(17), 2147\u20132164 (2011)","journal-title":"Discret. App. Math."},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"3338","DOI":"10.1016\/j.disc.2006.06.018","volume":"306","author":"H.-M. Xing","year":"2006","unstructured":"Xing, H.-M., Chen, X., Chen, X.-G.: A note on roman domination in graphs. Discret. Math.\u00a0306, 3338\u20133340 (2006)","journal-title":"Discret. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45278-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T18:39:36Z","timestamp":1558723176000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45278-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642452772","9783642452789"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45278-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}