{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T00:36:11Z","timestamp":1748392571418,"version":"3.40.5"},"reference-count":88,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T00:00:00Z","timestamp":1740441600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T00:00:00Z","timestamp":1740441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR project DISTANCIA","award":["(ANR-17-CE40-0015)","(ANR-17-CE40-0015)"],"award-info":[{"award-number":["(ANR-17-CE40-0015)","(ANR-17-CE40-0015)"]}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["10.55776\/Y1329"],"award-info":[{"award-number":["10.55776\/Y1329"]}],"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":[[2025,5]]},"DOI":"10.1007\/s00453-025-01300-4","type":"journal-article","created":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T13:19:12Z","timestamp":1740489552000},"page":"712-735","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Enumerating Minimal Solution Sets for Metric Graph Problems"],"prefix":"10.1007","volume":"87","author":[{"given":"Benjamin","family":"Bergougnoux","sequence":"first","affiliation":[]},{"given":"Oscar","family":"Defrain","sequence":"additional","affiliation":[]},{"given":"Fionn","family":"Mc Inerney","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,25]]},"reference":[{"key":"1300_CR1","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.4171\/dm\/421","volume":"18","author":"I Agol","year":"2013","unstructured":"Agol, I.: The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning). Doc. Math. 18, 1045\u20131087 (2013)","journal-title":"Doc. Math."},{"issue":"10","key":"1300_CR2","volume":"345","author":"J Ahn","year":"2022","unstructured":"Ahn, J., Jaffke, L., Kwon, O., Lima, P.T.: Well-partitioned chordal graphs. Discret. Math. 345(10), 112985 (2022)","journal-title":"Discret. Math."},{"key":"1300_CR3","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/j.tcs.2015.11.031","volume":"658","author":"KV Adaricheva","year":"2017","unstructured":"Adaricheva, K.V., Nation, J.B.: Discovery of the D-basis in binary tables based on hypergraph dualization. Theoret. Comput. Sci. 658, 307\u2013315 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"1300_CR4","volume-title":"Open Problems of the Lorentz Workshop, \u201cEnumeration Algorithms using Structure\u201d","author":"H Bodlaender","year":"2015","unstructured":"Bodlaender, H., Boros, E., Heggernes, P., Kratsch, D.: Open Problems of the Lorentz Workshop, \u201cEnumeration Algorithms using Structure\u2019\u2019. Department of Information and Computing Sciences Utrecht University, Utrecht, The Netherlands (2015)"},{"key":"1300_CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.jcta.2018.01.002","volume":"156","author":"H-J Bandelt","year":"2018","unstructured":"Bandelt, H.-J., Chepoi, V., Knauer, K.: COMs: Complexes of oriented matroids. J. Comb. Theory Ser. A 156, 195\u2013237 (2018)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"1300_CR6","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/1055-7903(92)90021-8","volume":"1","author":"H-J Bandelt","year":"1992","unstructured":"Bandelt, H.-J., Dress, A.W.M.: Split decomposition: a new and useful approach to phylogenetic analysis of distance data. Mol. Phylogenet. Evol. 1(3), 242\u2013252 (1992)","journal-title":"Mol. Phylogenet. Evol."},{"issue":"3","key":"1300_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3386686","volume":"16","author":"M Bonamy","year":"2020","unstructured":"Bonamy, M., Defrain, O., Heinrich, M., Pilipczuk, M., Raymond, J.-F.: Enumerating minimal dominating sets in $${K}_t$$-free and variants. ACM Trans. Algorithms 16(3), 1\u201323 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"1300_CR8","doi-asserted-by":"crossref","unstructured":"Bergougnoux, B, Defrain, O, Inerney, FM: Enumerating minimal solution sets for metric graph problems. In  50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024), (2024)","DOI":"10.1007\/978-3-031-75409-8_4"},{"key":"1300_CR9","unstructured":"Bonamy, M, Defrain, O, Micek, P, Nourine, L: Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets.  arXiv preprintarXiv:2004.07214, (2020)"},{"key":"1300_CR10","doi-asserted-by":"crossref","unstructured":"Bousquet, N, Deschamps, Q, Parreau, A: Metric dimension parameterized by treewidth in chordal graphs. In  Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023), volume 14093 of  Lecture Notes in Computer Science, pages 130\u2013142, (2023)","DOI":"10.1007\/978-3-031-43380-1_10"},{"issue":"12","key":"1300_CR11","doi-asserted-by":"crossref","first-page":"2168","DOI":"10.1109\/JSAC.2006.884015","volume":"24","author":"Z Beerliova","year":"2006","unstructured":"Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal\u2019ak, M., Ram, L.S.: Network discovery and verification. IEEE J. Sel. Area Comm. 24(12), 2168\u20132181 (2006)","journal-title":"IEEE J. Sel. Area Comm."},{"key":"1300_CR12","doi-asserted-by":"crossref","unstructured":"Boros, E, Elbassioni, Khaled, G, Vladimir: Algorithms for generating minimal blockers of perfect matchings in bipartite graphs and related problems. In  European Symposium on Algorithms (ESA 2004), pages 122\u2013133. Springer, (2004)","DOI":"10.1007\/978-3-540-30140-0_13"},{"key":"1300_CR13","unstructured":"Berge, C:  Hypergraphs: combinatorics of finite sets, volume\u00a045. Elsevier, (1984)"},{"issue":"2","key":"1300_CR14","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1137\/16M1057383","volume":"31","author":"R Belmonte","year":"2017","unstructured":"Belmonte, R., Fomin, F.V., Golovach, P.A., Ramanujan, M.S.: Metric dimension of bounded tree-length graphs. SIAM J. Discrete Math. 31(2), 1217\u20131243 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"1300_CR15","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jcss.2021.10.002","volume":"124","author":"T Bl\u00e4sius","year":"2022","unstructured":"Bl\u00e4sius, T., Friedrich, T., Lischeid, J., Meeks, K., Schirneck, M.: Efficiently enumerating hitting sets of hypergraphs arising in data profiling. J. Comput. Syst. Sci. 124, 192\u2013213 (2022)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1300_CR16","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E Boros","year":"1998","unstructured":"Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive boolean functions. Optim. Methods Softw. 10(2), 147\u2013156 (1998)","journal-title":"Optim. Methods Softw."},{"issue":"7","key":"1300_CR17","doi-asserted-by":"crossref","first-page":"1114","DOI":"10.1016\/j.jcta.2007.12.009","volume":"115","author":"Y Ben-Haim","year":"2008","unstructured":"Ben-Haim, Y., Gravier, S., Lobstein, A., Moncel, J.: Adaptive identification in graphs. J. Comb. Theory Ser. A 115(7), 1114\u20131126 (2008)","journal-title":"J. Comb. Theory Ser. A"},{"key":"1300_CR18","doi-asserted-by":"crossref","unstructured":"Birkhoff, G:  Lattice theory, volume\u00a025. American Mathematical Soc., (1940)","DOI":"10.1090\/coll\/025"},{"key":"1300_CR19","unstructured":"Brosse, C, Lagoutte, A, Limouzy, V, Mary, A, Pastor, L: Efficient enumeration of maximal split subgraphs and sub-cographs and related classes.  arXiv preprintarXiv:2007.01031, (2020)"},{"issue":"10","key":"1300_CR20","doi-asserted-by":"crossref","first-page":"2867","DOI":"10.1007\/s00453-020-00707-5","volume":"82","author":"J Bensmail","year":"2020","unstructured":"Bensmail, J., Mazauric, D.: Fionn Mc Inerney, Nicolas Nisse, and St\u00e9phane P\u00e9rennes Sequential metric dimension. Algorithmica 82(10), 2867\u20132901 (2020)","journal-title":"Algorithmica"},{"issue":"8","key":"1300_CR21","doi-asserted-by":"crossref","first-page":"2606","DOI":"10.1007\/s00453-021-00808-9","volume":"83","author":"\u00c9 Bonnet","year":"2021","unstructured":"Bonnet, \u00c9., Purohit, N.: Metric dimension parameterized by treewidth. Algorithmica 83(8), 2606\u20132633 (2021)","journal-title":"Algorithmica"},{"issue":"4","key":"1300_CR22","doi-asserted-by":"crossref","first-page":"2585","DOI":"10.1137\/22M1527817","volume":"37","author":"J Chalopin","year":"2023","unstructured":"Chalopin, J., Chepoi, V., Inerney, F.M., Ratel, S.V.: Sample compression schemes for balls in graphs. SIAM J. Discrete Math 37(4), 2585\u20132616 (2023)","journal-title":"SIAM J. Discrete Math"},{"key":"1300_CR23","doi-asserted-by":"crossref","unstructured":"Chalopin, J, Chepoi, V, Inerney, FM, Ratel, S: Non-clashing teaching maps for balls in graphs. In  Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), (2024)","DOI":"10.1137\/22M1527817"},{"key":"1300_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2022.01.003","volume":"127","author":"J Chalopin","year":"2022","unstructured":"Chalopin, J., Chepoi, V., Moran, S., Warmuth, M.K.: Unlabeled sample compression schemes and corner peelings for ample and maximum classes. J. Comput. Syst. Sci. 127, 1\u201328 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1300_CR25","unstructured":"Chakraborty, D, Das, S, Foucaud, F, Gahlawat, H, Lajou, D, Roy, B: Algorithms and complexity for geodetic Sets on planar and chordal graphs. In  31st International Symposium on Algorithms and Computation (ISAAC 2020), LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, (2020)"},{"key":"1300_CR26","doi-asserted-by":"crossref","unstructured":"Courcelle B, Engelfriet, J:  Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of  Encyclopedia of mathematics and its applications. Cambridge University Press, (2012)","DOI":"10.1017\/CBO9780511977619"},{"key":"1300_CR27","doi-asserted-by":"crossref","unstructured":"Chakraborty, D, Foucaud, F, Gahlawat, H, Ghosh, S\u00a0K, Roy, B: Hardness and approximation for the geodetic set problem in some graph classes. In  Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), volume 12016 of  Lecture Notes in Computer Science, pages 102\u2013115, Cham, 2020. Springer International Publishing","DOI":"10.1007\/978-3-030-39219-2_9"},{"key":"1300_CR28","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.tcs.2021.10.017","volume":"904","author":"K Casel","year":"2022","unstructured":"Casel, K., Fernau, H., Ghadikolaei, M.K., Monnot, J., Sikora, F.: On the complexity of solution extension of optimization problems. Theor. Comput. Sci. 904, 48\u201365 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1300_CR29","unstructured":"Chakraborty, D, Foucaud, F, Majumdar, D, Tale, P: Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover.  arXiv preprintarXiv:2402.08346, (2024)"},{"key":"1300_CR30","unstructured":"Conte, A, Grossi, R, Kant\u00e9, M\u00a0M., Marino, A, Uno, T, Wasa, K: Listing induced steiner subgraphs as a compact way to discover steiner trees in graphs. In  44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2019)"},{"key":"1300_CR31","unstructured":"Chandran, S, Issac, D, Karrenbauer, A: On the parameterized complexity of biclique cover and partition. In  11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume\u00a063 of  LIPIcs, pages 11:1\u201311:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2016)"},{"key":"1300_CR32","doi-asserted-by":"crossref","unstructured":"Conte, A, Kant\u00e9, M\u00a0M., Marino, A, Uno, T: Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs. In  International Workshop on Combinatorial Algorithms (IWOCA 2019), pages 148\u2013159. Springer, (2019)","DOI":"10.1007\/978-3-030-25005-8_13"},{"issue":"1","key":"1300_CR33","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1137\/20M1355434","volume":"36","author":"V Chepoi","year":"2022","unstructured":"Chepoi, V., Knauer, K., Philibert, M.: Ample completions of oriented matroids and complexes of uniform oriented matroids. SIAM J. Discret. Math. 36(1), 509\u2013535 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"1\u20133","key":"1300_CR34","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"12","key":"1300_CR35","doi-asserted-by":"crossref","first-page":"2675","DOI":"10.1016\/j.dam.2008.08.021","volume":"157","author":"B Courcelle","year":"2009","unstructured":"Courcelle, B.: Linear delay enumeration and monadic second-order logic. Discret. Appl. Math. 157(12), 2675\u20132700 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1300_CR36","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1137\/130947076","volume":"45","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: Known algorithms for edge clique cover are probably optimal. SIAM J. Comput. 45(1), 67\u201383 (2016)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1300_CR37","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"1300_CR38","unstructured":"Capelli, F, Strozecki, Y: Geometric amortization of enumeration algorithms. In  40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of  LIPIcs, pages 18:1\u201318:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2023)"},{"key":"1300_CR39","doi-asserted-by":"crossref","unstructured":"Diestel, R:  Graph Theory, volume 173 of  Graduate texts in mathematics. Springer, (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"1300_CR40","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.dam.2016.12.021","volume":"221","author":"B DasGupta","year":"2017","unstructured":"DasGupta, B., Mobasheri, N.: On optimal approximability results for computing the strong metric dimension. Discret. Appl. Math. 221, 18\u201324 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1300_CR41","unstructured":"Defrain, O, Nourine, L: Neighborhood inclusions for minimal dominating sets enumeration: Linear and polynomial delay algorithms in $${P}_7$$-free and $${P}_8$$-free chordal graphs. In  30th International Symposium on Algorithms and Computation (ISAAC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2019)"},{"key":"1300_CR42","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.tcs.2020.01.028","volume":"814","author":"O Defrain","year":"2020","unstructured":"Defrain, O., Nourine, L.: Dualization in lattices given by implicational bases. Theoret. Comput. Sci. 814, 169\u2013176 (2020)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"1300_CR43","doi-asserted-by":"crossref","DOI":"10.1016\/j.disc.2021.112399","volume":"344","author":"O Defrain","year":"2021","unstructured":"Defrain, O., Nourine, L., Vilmin, S.: Translating between the representations of a ranked convex geometry. Discret. Math. 344(7), 112399 (2021)","journal-title":"Discret. Math."},{"issue":"1","key":"1300_CR44","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.jcss.2016.06.006","volume":"83","author":"J D\u00edaz","year":"2017","unstructured":"D\u00edaz, J.: Pottonen, Olli, Serna, Maria, van Leeuwen, Erik Jan: Complexity of metric dimension on planar graphs. J. Comput. Syst. Sci. 83(1), 132\u2013158 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"1300_CR45","doi-asserted-by":"crossref","unstructured":"Ekim, T, Erey, A, Heggernes, P, van\u2019t H, Pim, MD: Computing minimum geodetic sets of proper interval graphs. In  Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), volume 7256 of  Lecture Notes in Computer Science, pages 279\u2013290. Springer, (2012)","DOI":"10.1007\/978-3-642-29344-3_24"},{"issue":"6","key":"1300_CR46","doi-asserted-by":"crossref","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24(6), 1278\u20131304 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1300_CR47","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/S009753970240639X","volume":"32","author":"T Eiter","year":"2003","unstructured":"Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32(2), 514\u2013537 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1300_CR48","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/050622250","volume":"23","author":"KM Elbassioni","year":"2009","unstructured":"Elbassioni, K.M.: Algorithms for dualization over products of partially ordered sets. SIAM J. Discret. Math. 23(1), 487\u2013510 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"1300_CR49","doi-asserted-by":"crossref","unstructured":"Elbassioni, K: On dualization over distributive lattices.  Discrete Mathematics & Theoretical Computer Science, 24(Discrete Algorithms), (2022)","DOI":"10.46298\/dmtcs.6742"},{"issue":"4","key":"1300_CR50","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1007\/s00453-014-9896-2","volume":"72","author":"L Epstein","year":"2015","unstructured":"Epstein, L., Levin, A., Woeginger, G.J.: The (weighted) metric dimension of graphs: hard and easy cases. Algorithmica 72(4), 1130\u20131171 (2015)","journal-title":"Algorithmica"},{"issue":"11","key":"1300_CR51","doi-asserted-by":"crossref","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T Eiter","year":"2008","unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: a brief survey. Discret. Appl. Math. 156(11), 2035\u20132049 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1300_CR52","doi-asserted-by":"crossref","first-page":"313","DOI":"10.7155\/jgaa.00360","volume":"19","author":"D Eppstein","year":"2015","unstructured":"Eppstein, D.: Metric dimension parameterized by max leaf number. J. Graph Algor. Appl. 19(1), 313\u2013323 (2015)","journal-title":"J. Graph Algor. Appl."},{"key":"1300_CR53","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.tcs.2018.09.027","volume":"767","author":"K Elbassioni","year":"2019","unstructured":"Elbassioni, K., Rauf, I., Ray, S.: A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs. Theoret. Comput. Sci. 767, 26\u201333 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1300_CR54","unstructured":"Foucaud, F, Galby, E, Khazaliya, L, Li, S, Inerney, FM, Sharma, R, Tale, P: Metric dimension and geodetic set parameterized by vertex cover.  arXiv preprint arXiv:2405.01344, (2024)"},{"key":"1300_CR55","unstructured":"Florent F, Esther G, Liana K, Shaohua L, Fionn M\u00a0I, Roohani S, and Prafullkumar T. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In  Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024), 2024"},{"issue":"3","key":"1300_CR56","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"ML Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21(3), 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"key":"1300_CR57","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1007\/s00453-016-0184-1","volume":"78","author":"F Foucaud","year":"2017","unstructured":"Foucaud, F., Mertzios, G.B., Naserasr, R., Parreau, A., Valicov, P.: Identification, location-domination and metric dimension on interval and permutation graphs II. Algorithms and complexity. Algorithmica 78, 914\u2013944 (2017)","journal-title":"Algorithmica"},{"issue":"2","key":"1300_CR58","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1007\/s00453-017-0289-1","volume":"80","author":"PA Golovach","year":"2018","unstructured":"Golovach, P.A., Heggernes, P., Kant\u00e9, M.M., Kratsch, D., S\u00e6ther, S.H., Villanger, Y.: Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica 80(2), 714\u2013741 (2018)","journal-title":"Algorithmica"},{"key":"1300_CR59","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2022.03.021","volume":"918","author":"T Gima","year":"2022","unstructured":"Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Otachi, Y.: Exploring the gap between treedepth and vertex cover through vertex integrity. Theoret. Comput. Sci. 918, 60\u201376 (2022)","journal-title":"Theoret. Comput. Sci."},{"key":"1300_CR60","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"4","key":"1300_CR61","doi-asserted-by":"crossref","first-page":"2241","DOI":"10.1137\/22M1510911","volume":"37","author":"E Galby","year":"2023","unstructured":"Galby, E., Khazaliya, L., Inerney, F.M., Sharma, R., Tale, P.: Metric dimension parameterized by feedback vertex set and other structural parameters. SIAM J. Discret. Math. 37(4), 2241\u20132264 (2023)","journal-title":"SIAM J. Discret. Math."},{"key":"1300_CR62","doi-asserted-by":"crossref","unstructured":"Gromov, M:  Hyperbolic Groups, pages 75\u2013263. Springer New York, New York, NY, (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"11","key":"1300_CR63","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0895-7177(93)90259-2","volume":"17","author":"F Harary","year":"1993","unstructured":"Harary, F., Loukakis, E., Tsouros, C.: The geodetic number of a graph. Math. Comput. Model. 17(11), 89\u201395 (1993)","journal-title":"Math. Comput. Model."},{"key":"1300_CR64","first-page":"191","volume":"2","author":"F Harary","year":"1976","unstructured":"Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combin. 2, 191\u2013195 (1976)","journal-title":"Ars Combin."},{"key":"1300_CR65","doi-asserted-by":"crossref","unstructured":"Hartung, S, Nichterlein, A: On the parameterized and approximation hardness of metric dimension. In  IEEE Conference on Computational Complexity (CCC 2013), pages 266\u2013276. IEEE, (2013)","DOI":"10.1109\/CCC.2013.36"},{"key":"1300_CR66","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1080\/10543409308835060","volume":"3","author":"M Johnson","year":"1993","unstructured":"Johnson, M.: Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Statist. 3, 203\u2013236 (1993)","journal-title":"J. Biopharm. Statist."},{"issue":"3","key":"1300_CR67","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1300_CR68","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.dam.2006.04.032","volume":"155","author":"L Khachiyan","year":"2007","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: Enumerating disjunctions and conjunctions of paths and cuts in reliability theory. Discret. Appl. Math. 155(2), 137\u2013149 (2007)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1300_CR69","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.tcs.2007.03.005","volume":"382","author":"L Khachiyan","year":"2007","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V.: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. Theoret. Comput. Sci. 382(2), 139\u2013150 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1300_CR70","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/18.661507","volume":"44","author":"MG Karpovsky","year":"1998","unstructured":"Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory 44(2), 599\u2013611 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"1300_CR71","first-page":"401","volume":"26","author":"L Kellerhals","year":"2022","unstructured":"Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. J. Gr. Algor. Appl. 26(4), 401\u2013419 (2022)","journal-title":"J. Gr. Algor. Appl."},{"key":"1300_CR72","unstructured":"Kant\u00e9, M\u00a0M., Khoshkhah, K, Pourmoradnasseri, M: Enumerating minimal transversals of hypergraphs without small holes. In  43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, (2018)"},{"key":"1300_CR73","doi-asserted-by":"crossref","unstructured":"Kant\u00e9, M\u00a0M., Limouzy, V, Mary, A, Nourine, L, Uno, T: A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In  International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), pages 138\u2013153. Springer, (2015)","DOI":"10.1007\/978-3-662-53174-7_11"},{"issue":"4","key":"1300_CR74","doi-asserted-by":"crossref","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"MM Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discret. Math. 28(4), 1916\u20131929 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1300_CR75","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1137\/15M1013389","volume":"30","author":"MM Kant\u00e9","year":"2016","unstructured":"Kant\u00e9, M.M., Nourine, L.: Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. SIAM J. Discret. Math. 30(1), 311\u2013326 (2016)","journal-title":"SIAM J. Discret. Math."},{"key":"1300_CR76","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.dam.2017.11.013","volume":"236","author":"The realization and the characterization problems","year":"2018","unstructured":"The realization and the characterization problems: Dorota Kuziak, Mar\u00eda Luz Puertas, Juan A Rodr\u00edguez-Vel\u00e1zquez, and Ismael G Yero. Strong resolving graphs. Discret. Appl. Math. 236, 270\u2013287 (2018)","journal-title":"Discret. Appl. Math."},{"issue":"11","key":"1300_CR77","doi-asserted-by":"crossref","first-page":"3110","DOI":"10.1007\/s00453-022-01005-y","volume":"84","author":"S Li","year":"2022","unstructured":"Li, S., Pilipczuk, M.: Hardness of metric dimension in graphs of constant treewidth. Algorithmica 84(11), 3110\u20133155 (2022)","journal-title":"Algorithmica"},{"key":"1300_CR78","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.tcs.2018.05.032","volume":"745","author":"M Mezzini","year":"2018","unstructured":"Mezzini, M.: Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. Theoret. Comput. Sci. 745, 63\u201374 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"1300_CR79","doi-asserted-by":"crossref","unstructured":"Mary, A, Strozecki, Y: Efficient enumeration of solutions produced by closure operations.  Discret. Math. Theor. Comput. Sci., 21(3), (2019)","DOI":"10.23638\/DMTCS-21-3-22"},{"issue":"3","key":"1300_CR80","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.dam.2006.06.009","volume":"155","author":"OR Oellermann","year":"2007","unstructured":"Oellermann, O.R., Peters-Fransen, J.: The strong metric dimension of graphs and digraphs. Discret. Appl. Math. 155(3), 356\u2013364 (2007)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"1300_CR81","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3), 237\u2013252 (1975)","journal-title":"Networks"},{"key":"1300_CR82","unstructured":"Slater, P\u00a0J.: Leaves of trees. In  Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 549\u2013559. Congressus Numerantium, No. XIV. Utilitas Mathematica, (1975)"},{"issue":"1","key":"1300_CR83","doi-asserted-by":"crossref","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":"2","key":"1300_CR84","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1287\/moor.1030.0070","volume":"29","author":"A Seb\u0151","year":"2004","unstructured":"Seb\u0151, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383\u2013393 (2004)","journal-title":"Math. Oper. Res."},{"key":"1300_CR85","unstructured":"Strozecki, Y: Enumeration complexity.  Bulletin of EATCS, 1(129), (2019)"},{"issue":"3","key":"1300_CR86","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"1300_CR87","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00285-019-01348-1","volume":"79","author":"RC Tillquist","year":"2019","unstructured":"Tillquist, R.C., Lladser, M.E.: Low-dimensional representation of genomic sequences. J. Math. Biol. 79, 1\u201329 (2019)","journal-title":"J. Math. Biol."},{"key":"1300_CR88","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/j.tcs.2016.03.018","volume":"658","author":"M Wild","year":"2017","unstructured":"Wild, M.: The joy of implications, aka pure horn formulas: mainly a survey. Theoret. Comput. Sci. 658, 264\u2013292 (2017)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01300-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01300-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01300-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T11:01:36Z","timestamp":1746702096000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01300-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,25]]},"references-count":88,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1300"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01300-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,2,25]]},"assertion":[{"value":"9 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}