{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:20Z","timestamp":1780822100277,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,4]],"date-time":"2016-02-04T00:00:00Z","timestamp":1454544000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["BeHard"],"award-info":[{"award-number":["BeHard"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00453-016-0127-x","type":"journal-article","created":{"date-parts":[[2016,2,4]],"date-time":"2016-02-04T04:55:37Z","timestamp":1454561737000},"page":"1181-1202","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["On the Computational Complexity of Vertex Integrity and Component Order Connectivity"],"prefix":"10.1007","volume":"76","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7228-6640","authenticated-orcid":false,"given":"P\u00e5l Gr\u00f8n\u00e5s","family":"Drange","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus","family":"Dregi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,4]]},"reference":[{"key":"127_CR1","doi-asserted-by":"crossref","unstructured":"Ben-Ameur, W., Mohamed-Sidi, M.-A., Neto, J.: The k-separator problem. In COCOON, volume 7936 of Lecture Notes in Computer Science, pp. 337\u2013348. Springer (2013)","DOI":"10.1007\/978-3-642-38768-5_31"},{"key":"127_CR2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0166-218X(92)90122-Q","volume":"37","author":"KS Bagga","year":"1992","unstructured":"Bagga, K.S., Beineke, L.W., Goddard, W.D., Lipman, M.J., Pippert, R.E.: A survey of integrity. Discret. Appl. Math. 37, 13\u201328 (1992)","journal-title":"Discret. Appl. Math."},{"issue":"38","key":"127_CR3","first-page":"13","volume":"1","author":"CA Barefoot","year":"1987","unstructured":"Barefoot, C.A., Entringer, R., Swart, H.: Vulnerability in graphs\u2014a comparative survey. J. Comb. Math. Comb. Comput. 1(38), 13\u201322 (1987)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"1","key":"127_CR4","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.tcs.2005.09.027","volume":"349","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci. 349(1), 22\u201330 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"127_CR5","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"127_CR6","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le Bang, V., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"issue":"1\u20132","key":"127_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$ k -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"127_CR8","first-page":"179","volume":"2","author":"LH Clark","year":"1987","unstructured":"Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Comb. Math. Comb. Comput 2, 179\u2013191 (1987)","journal-title":"J. Comb. Math. Comb. Comput"},{"key":"127_CR9","doi-asserted-by":"crossref","unstructured":"Drange, P.G., Dregi, M., van \u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. In ISAAC volume 8889 of Lecture Notes in Computer Science, pp. 285\u2013297. Springer (2014)","DOI":"10.1007\/978-3-319-13075-0_23"},{"key":"127_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"127_CR11","volume-title":"Graph Theory (Graduate Texts in Mathematics)","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory (Graduate Texts in Mathematics). Springer, New York (2005)"},{"key":"127_CR12","first-page":"23","volume":"6","author":"MR Fellows","year":"1989","unstructured":"Fellows, M.R., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Comb. Math. Comb. Comput. 6, 23\u201332 (1989)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"127_CR13","first-page":"895","volume":"12","author":"D Gross","year":"2013","unstructured":"Gross, D., Heinig, M., Iswara, L., Kazmierczak, L.W., Luttrell, K., Saccoman, J.T., Suffel, C.: A survey of component order connectivity models of graph theoretic networks. WSEAS Trans. Math. 12, 895\u2013910 (2013)","journal-title":"WSEAS Trans. Math."},{"key":"127_CR14","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman, New York (1979)"},{"issue":"1","key":"127_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"MC Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discret. Math. 43(1), 37\u201346 (1983)","journal-title":"Discret. Math."},{"issue":"2","key":"127_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C-W Ho","year":"1989","unstructured":"Ho, C.-W., Lee, R.C.T.: Counting clique trees and computing perfect elimination schemes in parallel. Inf. Process. Lett. 31(2), 61\u201368 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"127_CR17","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1016\/j.dam.2009.02.006","volume":"157","author":"L Ibarra","year":"2009","unstructured":"Ibarra, L.: The clique-separator graph for chordal graphs. Discret. Appl. Math. 157(8), 1737\u20131749 (2009)","journal-title":"Discret. Appl. Math."},{"key":"127_CR18","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of $$k$$ k -SAT. In IEEE Conference on Computational Complexity, pp. 237\u2013240. IEEE Computer Society (1999)","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"127_CR19","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"127_CR20","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0166-218X(96)00133-3","volume":"77","author":"D Kratsch","year":"1997","unstructured":"Kratsch, D., Kloks, T., M\u00fcller, H.: Measuring the vulnerability for classes of intersection graphs. Discret. Appl. Math. 77(3), 259\u2013270 (1997)","journal-title":"Discret. Appl. Math."},{"key":"127_CR21","first-page":"760","volume-title":"SODA","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Dana, R. (ed.) SODA, pp. 760\u2013776. SIAM, New York (2011)"},{"issue":"1","key":"127_CR22","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1080\/00207160701365721","volume":"85","author":"Y Li","year":"2008","unstructured":"Li, Y., Zhang, S., Zhang, Q.: Vulnerability parameters of split graphs. Int. J. Comput. Math. 85(1), 19\u201323 (2008)","journal-title":"Int. J. Comput. Math."},{"key":"127_CR23","first-page":"65","volume":"16","author":"S Ray","year":"1994","unstructured":"Ray, S., Deogun, J.S.: Computational complexity of weighted integrity. J. Comb. Math. Comb. Comput. 16, 65\u201373 (1994)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"127_CR24","first-page":"77","volume":"79","author":"S Ray","year":"2006","unstructured":"Ray, S., Kannan, R., Zhang, D., Jiang, H.: The weighted integrity problem is polynomial for interval graphs. Ars Comb. 79, 77\u201395 (2006)","journal-title":"Ars Comb."},{"issue":"1\u20133","key":"127_CR25","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0012-365X(98)00156-3","volume":"190","author":"GJ Woeginger","year":"1998","unstructured":"Woeginger, G.J.: The toughness of split graphs. Discret. Math. 190(1\u20133), 295\u2013297 (1998)","journal-title":"Discret. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0127-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0127-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0127-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T03:58:35Z","timestamp":1567569515000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0127-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["127"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0127-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,4]]}}}