The full list of publications acknowledging ANR GRALMECO can be consulted on HAL here.

Main publications of the project (sorted by publication date: most recent first)

• Laurent Beaudou, Jan Bok, Florent Foucaud, Daniel A. Quiroz, Jean-Florent Raymond. Profile and neighbourhood complexity of graphs with excluded minors and tree-structured graphs. Submitted manuscript, 2025. [hal | arXiv]
• Dibyayan Chakraborty, Florent Foucaud. Strong isometric path complexity of graphs: asymptotic minors, restricted holes, and graph operations. Submitted manuscript, 2025. [hal | arXiv]
• Julien Duron, Louis Esperet, Jean-Florent Raymond. Long induced paths in sparse graphs and graphs with forbidden patterns. Submitted manuscript, 2024. [hal]
  
• Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Metric Dimension and Geodetic Set parameterized by vertex cover. Journal of Computer and System Sciences 164:103850, 2027. [hal | arXiv | www]
  Conference version: Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Leibniz International Proceedings in Informatics 327, 33:1-33:20, 2025. [hal | arXiv (full version) | www]
• Laurent Beaudou, Florent Foucaud, Lucas Lorieau, Pranabendu Misra. Efficient algorithms for a drone multidepot segment covering problem. Proceedings of the 22nd International Symposium on Algorithmics of Wireless Networks (ALGOWIN 2026), to appear. Best Paper Award.
• Louis Esperet, Jean-Florent Raymond. Multiparty equality in the local broadcast model. Proceedings of the 33rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2026), Lecture Notes in Computer Science 16488:272-291, 2026. [hal | www]
  
• Laurent Beaudou, Florent Foucaud, Lucas Lorieau, Prafullkumar Tale. Structural parameterizations of Geodetic Set on directed (acyclic) graphs. Proceedings of the 51st conference on Mathematical Foundations of Computer Science (MFCS 2026), Leibniz International Proceedings in Informatics 386, 88:1-88:17, 2026. [hal | arXiv (full version) | www]
• Madhura Dutta, Florent Foucaud, Subhas C. Nandy. Algorithms and bounds for path covers of tree-structured graphs. Proceedings of the 32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science 16835:231-244, 2026. [hal | www]
• Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale. Parameterized complexity of Isometric Path Partition: treewidth and diameter. Proceedings of the 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026), Leibniz International Proceedings in Informatics 376, 11:1-11:18, 2026. [hal | arXiv (full version) | www]
• Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale. Algorithms and hardness for Geodetic Set on tree-like digraphs. Proceedings of the 12th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2026), Lecture Notes in Computer Science 16445:179-193, 2026. [www | hal]
• Julien Duron, Louis Esperet, Jean-Florent Raymond. Long induced paths and forbidden patterns: Polylogarithmic bounds. SIAM Journal on Discrete Mathematics 40(1):52-81, 2026. [hal | www]
  
• Antoine Dailly, Harmender Gahlawat, Zin Mar Myint. The Closed Geodetic Game: algorithms and strategies. Theoretical Computer Science 1085:116186, 2026. [www | hal]
  Conference version: Proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), Lecture Notes in Computer Science 15885:273-286, 2025. [www]
• Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gérard, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor. The Canadian Traveller Problem on unit-weighted and arbitrarily weighted outerplanar graphs. Theoretical Computer Science 1082:116096, 2026. [www | hal]
  Conference version: Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Leibniz International Proceedings in Informatics 306, 19:1-19:16, 2024. [hal | www]
• Florent Foucaud, Atrayee Majumdar, Tobias Mömke, Aida Roshany-Tabrizi. Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth. Theoretical Computer Science 1086:116226, 2026. Special issue for CALDAM 2025. [hal | arXiv | www]
  Conference version: Proceedings of the 11th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2025), Lecture Notes in Computer Science 15536:147-159, 2025. [hal | www]
• Florent Foucaud, Clara Marcille, Sandeep RB, Sagnik Sen, S Taruni. Algorithms and complexity for monitoring edge-geodetic sets in graphs. Information and Computation 312:105460, 2026. [hal | arXiv | www]
  Conference version: Proceedings of the 10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2024), Lecture Notes in Computer Science 14508:29-43, 2024. [hal | www]
• Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs. Information and Computation 311:105456, 2026. [hal | arXiv | www]
  Conference version: Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,7:1-7:15, 2020. [hal | arXiv (full version) | www]
• Florent Foucaud, Arti Pandey, Kaustav Paul. Characterizing optimal monitoring edge-geodetic sets for some structured graph classes. Discrete Applied Mathematics 389:92-105, 2026. [hal | arXiv | www]
• Antoine Dailly, Florent Foucaud, Anni Hakanen. Algorithms and hardness for Metric Dimension on digraphs. Journal of Computer and System Sciences 158:103776, 2026. Commemorative Special Issue for Rolf Niedermeier. [hal | arXiv | www]
  Conference version: Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). Lecture Notes in Computer Science 14093:232-245, 2023. [HAL | www]
• Sandip Das, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee. Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs. Discrete Applied Mathematics 386:184-194, 2026. Special issue for CALDAM 2023. [hal | arXiv | www]
  Conference version: Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:297-308, 2023. [HAL | www]
• Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, Yann Vaxès. Isometric path complexity of graphs. Discrete Mathematics 349(2):114743, 2026. [hal | arXiv | www]
  Conference version: Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Leibniz International Proceedings in Informatics 272,32:1-32:14, 2023. [HAL |arXiv (full version) | www]
• Subhadeep R. Dev, Sanjana Dey, Florent Foucaud, Krishna Narayanan, Lekshmi R S. Monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics 377:598-610, 2025. Special issue for CALDAM 2023. [hal | arXiv | www]
  Conference version: Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:245-256, 2023. [HAL | arXiv | www]
• Laurent Beaudou, Henry Echeverría, Florent Foucaud, Andrea Jiménez, Nikita Manuylenko, Anirudh Rachuri. A polynomial-time algorithm recognizing exact cubes of trees. Proceedings of the 13th Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS 2025), Procedia Computer Science 273:86-93, 2025. [hal | www]
• Dipayan Chakraborty, Soumen Nandi, Sagnik Sen and Supraja D K. A linear algorithm for radio k-coloring powers of paths having small diameter. Journal of Computer and System Sciences 147:103577, 2025. [hal | www]
  Conference version: Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), Lecture Notes in Computer Science 13889:148-159, 2023. [www]
• Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen. Distance-based (and path-based) covering problems for graphs of given cyclomatic number. Discrete Mathematics 348(11):114595, 2025. [hal | www]
  Conference version: Proceedings of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023). Lecture Notes in Computer Science 14292:132-146, 2023. [HAL | www]
• Florent Foucaud, Clara Marcille, Zin Mar Myint, Sandeep RB, Sagnik Sen, S Taruni. Bounds and extremal graphs for monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics 366:106-119, 2025. [hal | arXiv | www]
  Conference version: Proceedings of the 10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2024), Lecture Notes in Computer Science 14508:29-43, 2024. [hal | www]
• Tapas Das, Florent Foucaud, Clara Marcille, Pavan PD, Sagnik Sen. Monitoring arc-geodetic sets of oriented graphs. Theoretical Computer Science 1031:115079, 2025. [hal | arXiv | www]
• Henning Fernau, Florent Foucaud, Kevin Mann, Utkarsh Padariya, Rajath Rao K.N.. Parameterizing path partitions. Theoretical Computer Science 1028:115029, 2025. Special issue for selected papers of CIAC 2023. [hal | arXiv | www]
  Conference version: Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898:187-201, 2023. [arXiv (full version) | www]
• Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing. Algorithms and complexity for path covers of temporal DAGs. Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Leibniz International Proceedings in Informatics 306, 38:1-38:17, 2024. [hal | arXiv (full version) | www]
• Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin and Jean-Florent Raymond. Local certification of geometric graph classes. Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Leibniz International Proceedings in Informatics 306, 38:1-38:17, 2024. [hal | arXiv (full version) | www]
• Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond. Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius. Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) Leibniz International Proceedings in Informatics 327, 11:1-11:18, 2024. [hal | arXiv (full version) | www]
• Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin and Jean-Florent Raymond. Local certification of geometric graph classes. Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Leibniz International Proceedings in Informatics 306, 38:1-38:17, 2024. [hal | arXiv (full version) | www]
• Jan Bok, Antoine Dailly, Tuomo Lehtilä. Resolving Sets in Temporal Graphs. Proceedings of the 35th International Workshop on Combinatorial Algorithms (IWOCA 2024), Lecture Notes in Computer Science 14764:287-300, 2024. [www]. [hal | www]
• Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. Proceedings of the 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024), Leibniz International Proceedings in Informatics 297, 66:1-66:19, 2024. [hal | arXiv (full version) | www]
• Dipayan Chakraborty, Florent Foucaud, Soumen Nandi, Sagnik Sen, D K Supraja. On locating and neighbor-locating colorings of sparse graphs. Discrete Applied Mathematics 358:366-381, 2024. [hal | arXiv | www]
  Conference version: Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:121-133, 2023. [hal | www]
• Anni Hakanen, Ville Junnila, Tero Laihonen and Ismael G. Yero. On the unicyclic graphs having vertices that belong to all their (strong) metric bases. Discrete Applied Mathematics 353:191-207, 2024. [HAL | arXiv]
• Anni Hakanen and Ismael G. Yero. Complexity and equivalency of multiset dimension and ID-colorings. Fundamenta Informaticae 191(3-4):315-330, 2024. [HAL | arXiv]
• Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca. On graphs coverable by k shortest paths. SIAM Journal on Discrete Mathematics 38(2):1840-1862, 2024. [arXiv | hal | www]
  Conference version: Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248,40:1-40:15, 2022. [HAL | www]
• Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi and Jean-Florent Raymond. Lower Bound for Constant-Size Local Certification. Theoretical Computer Science 971:114068, 2023. [HAL | www]
  Conference version: Proceedings of the 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2022), Lecture Notes in Computer Science 13751:239-253, 2022. [HAL | www]
• Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. Journal of Combinatorial Theory, Series B 166:30-49, 2023. [HAL | arXiv]
• Claire Hilaire and Jean-Florent Raymond. Long induced paths in minor-closed graph classes and beyond. The Electronic Journal of Combinatorics P1.18, 2023. [hal | arXiv | www]
• Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat and Subir Kumar Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248,12:1-12:17, 2022. [HAL (full version) | www]