{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:11Z","timestamp":1747541051027,"version":"3.40.5"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_13","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:13Z","timestamp":1747468033000},"page":"187-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Structural Parameterization of\u00a0Locating-Dominating Set and\u00a0Test Cover"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7169-7288","authenticated-orcid":false,"given":"Dipayan","family":"Chakraborty","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8198-693X","authenticated-orcid":false,"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9753-0523","authenticated-orcid":false,"given":"Prafullkumar","family":"Tale","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2021.01.033","volume":"860","author":"A Agrawal","year":"2021","unstructured":"Agrawal, A., Kanesh, L., Saurabh, S., Tale, P.: Paths to trees and cacti. Theor. Comput. Sci. 860, 98\u2013116 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.dam.2019.08.001","volume":"281","author":"GR Argiroffo","year":"2020","unstructured":"Argiroffo, G.R., Bianchi, S.M., Lucarini, Y., Wagler, A.K.: Linear-time algorithms for three domination-based separation problems in block graphs. Discret. Appl. Math. 281, 6\u201341 (2020)","journal-title":"Discret. Appl. Math."},{"issue":"8","key":"13_CR3","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1007\/s00453-020-00674-x","volume":"82","author":"F Barbero","year":"2020","unstructured":"Barbero, F., Isenmann, L., Thiebaut, J.: On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. Algorithmica 82(8), 2243\u20132266 (2020)","journal-title":"Algorithmica"},{"issue":"3","key":"13_CR4","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1137\/15M1039584","volume":"30","author":"M Basavaraju","year":"2016","unstructured":"Basavaraju, M., Francis, M.C., Ramanujan, M.S., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discret. Math. 30(3), 1401\u20131423 (2016)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"13_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.jcss.2005.02.001","volume":"71","author":"P Berman","year":"2005","unstructured":"Berman, P., DasGupta, B., Kao, M.: Tight approximability results for test set problems in bioinformatics. J. Comput. Syst. Sci. 71(2), 145\u2013162 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"13_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0095-8956(72)90025-1","volume":"12","author":"JA Bondy","year":"1972","unstructured":"Bondy, J.A.: Induced subsets. J. Comb. Theory, Ser. B 12(2), 201\u2013202 (1972)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"1\u20133","key":"13_CR7","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"K Bontridder","year":"2003","unstructured":"Bontridder, K., et al.: Approximation algorithms for the test cover problem. Math. Program. 98(1\u20133), 477\u2013491 (2003)","journal-title":"Math. Program."},{"key":"13_CR8","unstructured":"Cappelle, M.R., de\u00a0C.\u00a0M.\u00a0Gomes, G., dos Santos, V.F.: Parameterized algorithms for locating-dominating sets. CoRR abs\/2011.14849 (2020)"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Cappelle, M.R., Gomes, G.C.M., dos Santos, V.F.: Parameterized algorithms for locating-dominating sets. In: Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, (LAGOS). Procedia Computer Science, vol.\u00a0195, pp. 68\u201376 (2021)","DOI":"10.1016\/j.procs.2021.11.012"},{"key":"13_CR10","unstructured":"Chakraborty, D., Foucaud, F., Majumdar, D., Tale, P.: Structural parameterization of locating-dominating set and test cover. CoRR abs\/2411.17948 (2024)"},{"key":"13_CR11","unstructured":"Chakraborty, D., Foucaud, F., Majumdar, D., Tale, P.: Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. In: 35th International Symposium on Algorithms and Computation, (ISAAC). LIPIcs, vol.\u00a0322, pp. 19:1\u201319:18 (2024)"},{"key":"13_CR12","unstructured":"Chakraborty, D., Hakanen, A., Lehtil\u00e4, T.: The $$n\/2$$-bound for locating-dominating sets in subcubic graphs. CoRR abs\/2406.19278 (2024)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Nguyen, S.H.: On finding optimal discretizations for two attributes. In: Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, vol.\u00a01424, pp. 537\u2013544 (1998)","DOI":"10.1007\/3-540-69115-4_74"},{"key":"13_CR14","first-page":"135","volume":"56","author":"C Colbourn","year":"1987","unstructured":"Colbourn, C., Slater, P.J., Stewart, L.K.: Locating-dominating sets in series-parallel networks. Congr. Numer. 56, 135\u2013162 (1987)","journal-title":"Congr. Numer."},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s00453-014-9948-7","volume":"74","author":"R Crowston","year":"2016","unstructured":"Crowston, R., Gutin, G.Z., Jones, M., Muciaccia, G., Yeo, A.: Parameterizations of test cover with bounded test sizes. Algorithmica 74(1), 367\u2013384 (2016)","journal-title":"Algorithmica"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-642-32589-2_27","volume-title":"Mathematical Foundations of Computer Science 2012","author":"R Crowston","year":"2012","unstructured":"Crowston, R., Gutin, G., Jones, M., Saurabh, S., Yeo, A.: Parameterized study of the test cover problem. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 283\u2013295. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32589-2_27"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition, Graduate Texts in Mathematics, vol.\u00a0173. Springer, Cham (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"13_CR19","unstructured":"Foucaud, F., et al.: Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In: 51st International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol.\u00a0297, pp. 66:1\u201366:19 (2024)"},{"key":"13_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability - A Guide to NP-Completeness. W.H, Freeman and Company (1979)"},{"issue":"4","key":"13_CR21","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.ipl.2012.12.008","volume":"113","author":"GZ Gutin","year":"2013","unstructured":"Gutin, G.Z., Muciaccia, G., Yeo, A.: (non-)existence of polynomial kernels for the test cover problem. Inf. Process. Lett. 113(4), 123\u2013126 (2013)","journal-title":"Inf. Process. Lett."},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BFb0028546","volume-title":"STACS 98","author":"M Habib","year":"1998","unstructured":"Habib, M., Paul, C., Viennoti, L.: A synthesis on partition refinement: A useful routine for strings, graphs, Boolean matrices and automata. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 25\u201338. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0028546"},{"key":"13_CR23","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. In: 41st International Symposium on Theoretical Aspects of Computer Science, (STACS). LIPIcs, vol.\u00a0289, pp. 40:1\u201340:18 (2024)"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"401","DOI":"10.7155\/jgaa.00601","volume":"26","author":"L Kellerhals","year":"2022","unstructured":"Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. J. Graph Algorithms Appl. 26(4), 401\u2013419 (2022)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"13_CR25","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1109\/12.214691","volume":"42","author":"N Rao","year":"1993","unstructured":"Rao, N.: Computational complexity issues in operative diagnosis of graph-based systems. IEEE Trans. Comput. 42(4), 447\u2013457 (1993)","journal-title":"IEEE Trans. Comput."},{"key":"13_CR26","first-page":"75","volume":"22","author":"A R\u00e9nyi","year":"1961","unstructured":"R\u00e9nyi, A.: On random generating elements of a finite Boolean algebra. Acta Scientiarum Mathematicarum Szeged 22, 75\u201381 (1961)","journal-title":"Acta Scientiarum Mathematicarum Szeged"},{"issue":"1","key":"13_CR27","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/net.3230170105","volume":"17","author":"PJ Slater","year":"1987","unstructured":"Slater, P.J.: Domination and location in acyclic graphs. Networks 17(1), 55\u201364 (1987)","journal-title":"Networks"},{"issue":"4","key":"13_CR28","first-page":"445","volume":"22","author":"PJ Slater","year":"1988","unstructured":"Slater, P.J.: Dominating and reference sets in a graph. J. Math. Phys. Sci. 22(4), 445\u2013455 (1988)","journal-title":"J. Math. Phys. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:18Z","timestamp":1747468038000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}