{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:12Z","timestamp":1740109272939,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:00:00Z","timestamp":1502668800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P25607","Y698"],"award-info":[{"award-number":["P25607","Y698"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00453-017-0358-5","type":"journal-article","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T18:14:42Z","timestamp":1502734482000},"page":"2909-2940","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Complexity of Secure Sets"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2898-2830","authenticated-orcid":false,"given":"Bernhard","family":"Bliem","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,14]]},"reference":[{"key":"358_CR1","doi-asserted-by":"crossref","unstructured":"Abseher, M., Bliem, B., Charwat, G., Dusberger, F., Woltran, S.: Computing secure sets in graphs using answer set programming. J. Log. Comput. (2015, accepted)","DOI":"10.1093\/logcom\/exv060"},{"issue":"2","key":"358_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discrete Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"7","key":"358_CR3","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/j.dam.2010.11.003","volume":"159","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discrete Appl. Math. 159(7), 498\u2013508 (2011)","journal-title":"Discrete Appl. Math."},{"key":"358_CR4","doi-asserted-by":"crossref","unstructured":"Bliem, B., Woltran, S.: Complexity of secure sets. In: Mayr, E.W. (ed.) Revised Papers of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), June 17\u201319, 2015, Garching, Germany. Lecture Notes in Computer Science, vol. 9224, pp. 64\u201377. Springer (2016)","DOI":"10.1007\/978-3-662-53174-7_5"},{"issue":"1\u20132","key":"358_CR5","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"6","key":"358_CR6","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"358_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Discovering treewidth. In: Vojt\u00e1s, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2005), January 22\u201328, 2005, Liptovsk\u00fd J\u00e1n, Slovakia. Lecture Notes in Computer Science, vol. 3381, pp. 1\u201316. Springer (2005)","DOI":"10.1007\/978-3-540-30577-4_1"},{"issue":"3","key":"358_CR8","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput. 208(3), 259\u2013275 (2010)","journal-title":"Inf. Comput."},{"key":"358_CR9","unstructured":"Boja\u0144czyk, M., Pilipczuk, M.: Optimizing tree decompositions in MSO. In: Vollmer, H., Vall\u00e9e, B. (eds.) Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), March 8\u201311, 2017, Hannover, Germany. LIPIcs \u2013 Leibniz International Proceedings in Informatics, vol. 66, pp. 15:1\u201315:13. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"issue":"12","key":"358_CR10","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/2043174.2043195","volume":"54","author":"G Brewka","year":"2011","unstructured":"Brewka, G., Eiter, T., Truszczy\u0144ski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92\u2013103 (2011)","journal-title":"Commun. ACM"},{"issue":"13","key":"358_CR11","doi-asserted-by":"crossref","first-page":"1708","DOI":"10.1016\/j.dam.2007.03.009","volume":"155","author":"RC Brigham","year":"2007","unstructured":"Brigham, R.C., Dutton, R.D., Hedetniemi, S.T.: Security in graphs. Discrete Appl. Math. 155(13), 1708\u20131714 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"358_CR12","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"358_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"358_CR14","doi-asserted-by":"crossref","unstructured":"Dermaku, A., Ganzow, T., Gottlob, G., McMahan, B.J., Musliu, N., Samer, M.: Heuristic methods for hypertree decomposition. In: Gelbukh, A.F., Morales, E.F. (eds.) Proceedings of the 7th Mexican International Conference on Artificial Intelligence (MICAI 2008), October 27\u201331, 2008, Atizap\u00e1n de Zaragoza, Mexico. Lecture Notes in Computer Science, vol. 5317, pp. 1\u201311. Springer (2008)","DOI":"10.1007\/978-3-540-88636-5_1"},{"key":"358_CR15","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC 2008), May 14\u201316, 2008, Victoria, Canada. Lecture Notes in Computer Science, vol. 5018, pp. 78\u201390. Springer (2008)","DOI":"10.1007\/978-3-540-79723-4_9"},{"key":"358_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"358_CR17","first-page":"161","volume":"189","author":"RI Enciso","year":"2008","unstructured":"Enciso, R.I., Dutton, R.D.: Parameterized complexity of secure sets. Congr. Numer. 189, 161\u2013168 (2008)","journal-title":"Congr. Numer."},{"issue":"3","key":"358_CR18","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/2.989932","volume":"35","author":"S Lawrence","year":"2002","unstructured":"Lawrence, S., Giles, C.L., Coetzee, F.: Self-organization and identification of web communities. IEEE Comput. 35(3), 66\u201371 (2002)","journal-title":"IEEE Comput."},{"key":"358_CR19","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, New York (2006)"},{"key":"358_CR20","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S.T., Henning, M.A.: Global defensive alliances in graphs. Electron. J. Comb. 10 (2003)","DOI":"10.37236\/1740"},{"key":"358_CR21","doi-asserted-by":"crossref","unstructured":"Ho, Y.Y.: Global Secure Sets of Trees and Grid-Like Graphs. PhD thesis, University of Central Florida, Orlando, FL, USA (2011)","DOI":"10.1016\/j.dam.2010.12.013"},{"issue":"3","key":"358_CR22","first-page":"373","volume":"6","author":"YY Ho","year":"2009","unstructured":"Ho, Y.Y., Dutton, R.D.: Rooted secure sets of trees. AKCE Int. J. Graphs Comb. 6(3), 373\u2013392 (2009)","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"358_CR23","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Lecture Notes in Computer Science. Springer, New York, NY, USA (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"1","key":"358_CR24","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(92)90208-R","volume":"36","author":"A Kornai","year":"1992","unstructured":"Kornai, A., Tuza, Z.: Narrowness, pathwidth, and their application in natural language processing. Discrete Appl. Math. 36(1), 87\u201392 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"29","key":"358_CR25","doi-asserted-by":"crossref","first-page":"3487","DOI":"10.1016\/j.tcs.2011.02.038","volume":"412","author":"D Marx","year":"2011","unstructured":"Marx, D.: Complexity of clique coloring and related problems. Theor. Comput. Sci. 412(29), 3487\u20133500 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"358_CR26","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"issue":"1","key":"358_CR27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"358_CR28","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s10472-005-0432-6","volume":"43","author":"S Szeider","year":"2005","unstructured":"Szeider, S.: Generalizations of matched CNF formulas. Ann. Math. Artif. Intell. 43(1), 223\u2013238 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"key":"358_CR29","unstructured":"Szeider, S.: Not so easy problems for tree decomposable graphs. CoRR, arXiv:1107.1177 (2011)"},{"issue":"2","key":"358_CR30","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree-width and good register allocation. Inf. Comput. 142(2), 159\u2013181 (1998)","journal-title":"Inf. Comput."},{"key":"358_CR31","unstructured":"Yero, I.G., Rodr\u00edguez-Vel\u00e1zquez, J.A.: Defensive alliances in graphs: a survey. CoRR, arXiv:1308.2096 (2013)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0358-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0358-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0358-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T06:11:26Z","timestamp":1602742286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0358-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,14]]},"references-count":31,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["358"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0358-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,8,14]]}}}