{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T11:58:52Z","timestamp":1768305532247,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031522123","type":"print"},{"value":"9783031522130","type":"electronic"}],"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-52213-0_13","type":"book-chapter","created":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T10:02:29Z","timestamp":1705140149000},"page":"179-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Eternal Connected Vertex Cover Problem in\u00a0Graphs: Complexity and\u00a0Algorithms"],"prefix":"10.1007","author":[{"given":"Kaustav","family":"Paul","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arti","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,14]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Araki, H., Fujito, T., Inoue, S.: On the eternal vertex cover numbers of generalized trees. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 98, 1153\u20131160 (2015)","DOI":"10.1587\/transfun.E98.A.1153"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.dam.2021.02.004","volume":"319","author":"J Babu","year":"2022","unstructured":"Babu, J., Chandran, L.S., Francis, M., Prabhakaran, V., Rajendraprasad, D., Warrier, N.J.: On graphs whose eternal vertex cover number and vertex cover number coincide. Discret. Appl. Math. 319, 171\u2013182 (2022)","journal-title":"Discret. Appl. Math."},{"key":"13_CR3","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-031-09574-0_5","volume-title":"Computer Science - Theory and Applications","author":"J Babu","year":"2022","unstructured":"Babu, J., Misra, N., Nanoti, S.G.: Eternal vertex cover on bipartite graphs. In: Kulikov, A.S., Raskhodnikova, S. (eds.) CSR 2022. LNCS, vol. 13296, pp. 64\u201376. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-09574-0_5"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"2482","DOI":"10.1007\/s10878-021-00764-8","volume":"44","author":"J Babu","year":"2022","unstructured":"Babu, J., Prabhakaran, V.: A new lower bound for the eternal vertex cover number of graphs. J. Comb. Optim. 44, 2482\u20132498 (2022)","journal-title":"J. Comb. Optim."},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2021.08.018","volume":"890","author":"J Babu","year":"2021","unstructured":"Babu, J., Prabhakaran, V., Sharma, A.: A substructure based lower bound for eternal vertex cover number. Theor. Comput. Sci. 890, 87\u2013104 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B Escoffier","year":"2010","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algorithms 8, 36\u201349 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: complexity and algorithms. J. Discrete Algorithms 7, 149\u2013167 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0166-218X(97)00126-1","volume":"84","author":"DC Fisher","year":"1998","unstructured":"Fisher, D.C., McKenna, P.A., Boyer, E.D.: Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski\u2019s graphs. Discret. Appl. Math. 84, 93\u2013105 (1998)","journal-title":"Discret. Appl. Math."},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"2742","DOI":"10.1016\/j.disc.2010.05.028","volume":"310","author":"H Fleischner","year":"2010","unstructured":"Fleischner, H., Sabidussi, G., Sarvanov, V.I.: Maximum independent sets in 3- and 4-regular Hamiltonian graphs. Discret. Math. 310, 2742\u20132749 (2010)","journal-title":"Discret. Math."},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.ipl.2010.05.029","volume":"110","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Gaspers, S., Golovach, P.A., Kratsch, D., Saurabh, S.: Parameterized algorithm for eternal vertex cover. Inf. Process. Lett. 110, 702\u2013706 (2010)","journal-title":"Inf. Process. Lett."},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-030-59267-7_16","volume-title":"Theory and Applications of Models of Computation","author":"T Fujito","year":"2020","unstructured":"Fujito, T., Nakamura, T.: Eternal connected vertex cover problem. In: Chen, J., Feng, Q., Xu, J. (eds.) TAMC 2020. LNCS, vol. 12337, pp. 181\u2013192. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59267-7_16"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is \\$np\\$-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Discret. Appl. Math. 27, 85\u201399 (1990)","journal-title":"Discret. Appl. Math."},{"key":"13_CR14","first-page":"235","volume":"45","author":"WF Klostermeyer","year":"2009","unstructured":"Klostermeyer, W.F., Mynhardt, C.M.: Edge protection in graphs. Australas. J Comb. 45, 235\u2013250 (2009)","journal-title":"Australas. J Comb."},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/s10878-019-00403-3","volume":"38","author":"Y Li","year":"2019","unstructured":"Li, Y., Wang, W., Yang, Z.: The connected vertex cover problem in k-regular graphs. J. Comb. Optim. 38, 635\u2013645 (2019)","journal-title":"J. Comb. Optim."},{"key":"13_CR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-031-27051-2_21","volume-title":"WALCOM Algorithms and Computation","author":"K Paul","year":"2023","unstructured":"Paul, K., Pandey, A.: Some algorithmic results for eternal vertex cover problem in graphs. In: Lin, C.C., Lin, B.M.T., Liotta, G. (eds.) WALCOM 2023. LNCS, vol. 13973, pp. 242\u2013253. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-27051-2_21"},{"key":"13_CR17","unstructured":"Priyadarsini, P.K., Hemalatha, T.: Connected vertex cover in 2-connected planar graph with maximum degree 4 is NP-complete. Int. J. Math. Comput. Phys. Electr. Comput. Eng, 1, 570\u2013573 (2007)"},{"key":"13_CR18","unstructured":"Stewart, L.: Cographs: a Class of Tree Representable Graphs. University of Toronto, Department of Computer Science (1978)"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discret. Math. 72, 355\u2013360 (1988)","journal-title":"Discret. Math."},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Watanabe, T., Kajita, S., Onaga, K.: Vertex covers and connected vertex covers in 3-connected graphs. In: 1991 IEEE International Symposium on Circuits and Systems (ISCAS), vol. 2, pp. 1017\u20131020 (1991)","DOI":"10.1109\/ISCAS.1991.176537"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-52213-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T05:22:40Z","timestamp":1768281760000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-52213-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031522123","9783031522130"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-52213-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"14 January 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bhilai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","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":"15 February 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.iitbhilai.ac.in\/caldam2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}