Navigate down: Research papers - Theses - Other material

Research papers

Submitted

Tapas Das, FF, Clara Marcille, Pavan PD and Sagnik Sen. Monitoring arc-geodetic sets of oriented graphs. Manuscript, 2024. [arXiv]
Dipayan Chakraborty, FF and Michael A. Henning. Identifying open codes in trees and 4-cycle-free graphs of given maximum degree. Manuscript, 2024. [arXiv]
Dipayan Chakraborty, FF, Michael A. Henning and Tuomo Lehtilä. Identifying codes in triangle-free graphs of bounded maximum degree. Manuscript, 2024. [arXiv]
Dipayan Chakraborty, FF, Michael A. Henning and Tuomo Lehtilä. Identifying codes in graphs of given maximum degree: characterizing trees. Manuscript, 2024. [arXiv]
Dipayan Chakraborty, FF, Diptapriyo Majumdar and Prafullkumar Tale. Structural parameterization of Locating-Dominating Set and Test Cover. Manuscript, 2024. [arXiv]

FF, Clara Marcille, Sandeep RB, Sagnik Sen and S Taruni. Algorithms and complexity for monitoring edge-geodetic sets in graphs. Manuscript, 2024. [arXiv]
Based on parts of the results of a preliminary conference version presented at CALDAM 2024.

Dipayan Chakraborty, FF, Diptapriyo Majumdar and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-Dominating Set and Test Cover. Manuscript, 2024. [arXiv]
A preliminary conference version was presented at ISAAC 2024.

Dibyayan Chakraborty, FF and Anni Hakanen. Distance-based (and path-based) covering problems for graphs of given cyclomatic number. Manuscript, 2024.
A preliminary conference version was presented at FCT 2023.

FF, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. Manuscript, 2024. [arXiv]
A preliminary conference version was presented at ICALP 2024.

Sandip Das, FF, Sk Samim Islam and Joydeep Mukherjee. Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs. Manuscript, 2023. [arXiv]
A preliminary conference version was presented at CALDAM 2023.

Dibyayan Chakraborty, Jérémie Chalopin, FF and Yann Vaxès. Isometric path complexity of graphs. Manuscript, 2023. [arXiv]
A preliminary conference version was presented at MFCS 2023.

Subhadeep R. Dev, Sanjana Dey, FF, Krishna Narayanan and Lekshmi R S. Monitoring edge-geodetic sets in graphs. Manuscript, 2023. [arXiv]
A preliminary conference version was presented at CALDAM 2023.

Antoine Dailly, FF and Anni Hakanen. Algorithms and hardness for Metric Dimension on digraphs. Manuscript, 2023. [arXiv]
A preliminary conference version was presented at WG 2023.

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, FF, Harmender Gahlawat and Subir Kumar Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. Manuscript, 2023. [hal]
A preliminary conference version was presented at ISAAC 2022.

Laurent Beaudou, FF, Florent Madelaine, Lhouari Nourine and Gaétan Richard. Complexity of conjunctive regular path query homomorphisms. Manuscript, 2023. [arXiv]
A preliminary conference version was presented at CIE 2019.

Dibyayan Chakraborty, Sandip Das, FF, Harmender Gahlawat and Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs. Manuscript, 2022. [hal]
Based on parts of the results of a preliminary conference version presented at ISAAC 2020.

Accepted

[C35] FF, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Metric Dimension and Geodetic Set parameterized by vertex cover. Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Leibniz International Proceedings in Informatics, to appear. [arXiv (full version)]
[C34] FF, Atrayee Majumder, Tobias Mömke, Aida Roshany-Tabrizi. Polynomial-time algorithms for PATH COVER on trees and graphs of bounded treewidth. Proceedings of the 10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2025), Lecture Notes in Computer Science, to appear.
[J54] FF, Clara Marcille, Zin Mar Myint, Sandeep RB, Sagnik Sen and S Taruni. Bounds and extremal graphs for monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics, to appear. [hal | arXiv]
Based on parts of the results of a preliminary conference version presented at CALDAM 2024.

2025

[J53] Henning Fernau, FF, Kevin Mann, Utkarsh Padariya and Rajath Rao K.N.. Parameterizing path partitions. Theoretical Computer Science 1028:115029, 2025. Special issue for selected papers of CIAC 2023. [pdf | hal | arXiv | www]
A preliminary conference version was presented at CIAC 2023.

2024

[J52] Dipayan Chakraborty, FF, Soumen Nandi, Sagnik Sen and D K Supraja. On locating and neighbor-locating colorings of sparse graphs. Discrete Applied Mathematics 358:366-381, 2024. [pdf | hal | arXiv | www]
A preliminary conference version was presented at CALDAM 2023.
[J51] Dipayan Chakraborty, FF, Anni Hakanen, Michael A. Henning and Annegret K. Wagler. Progress towards the two-thirds conjecture on locating-total dominating sets. Discrete Mathematics 347(12):114176, 2024. [pdf | hal | arXiv | www]
[J50] Dipayan Chakraborty, FF, Aline Parreau and Annegret K. Wagler. On three domination-based identification problems in block graphs. Fundamenta Informaticae 191(3-4):197-229, 2024. Special issue in honour of Iiro Honkala's 60th birthday. [pdf | hal | arXiv | www]
A preliminary conference version was presented at CALDAM 2023.
[J49] Maël Dumas, FF, Anthony Perez and Ioan Todinca. On graphs coverable by k shortest paths. SIAM Journal on Discrete Mathematics 38(2):1840-1862, 2024. [pdf | arXiv | hal | www]
A preliminary conference version was presented at ISAAC 2022.
[J48] FF, Narges Ghareghani and Pouyeh Sharifani. Extremal digraphs for open neighbourhood location-domination and identifying codes. Discrete Applied Mathematics 347:62-74, 2024. [pdf | arXiv | hal | www]
[J47] Édouard Bonnet, FF, Tuomo Lehtilä and Aline Parreau. Neighbourhood complexity of graphs of bounded twin-width. European Journal of Combinatorics 115:103772, 2024. [pdf | arXiv | hal | www]
[J46] Laurent Beaudou, Caroline Brosse, Oscar Defrain, FF, Aurélie Lagoutte, Vincent Limouzy and Lucas Pastor. Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. Discrete Mathematics & Theoretical Computer Science 25(2):25, 2024. [pdf | arXiv | hal | www]
[C33] Dipayan Chakraborty, FF, Diptapriyo Majumdar and Prafullkumar Tale. Tight (double) exponential bounds for identification problems: Locating-Dominating Set and Test Cover. Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024), Leibniz International Proceedings in Informatics 322,19:1-19:18, 2024. [pdf | hal | arXiv (full version) | www]
The full version is submitted to a journal.
[C32] Dibyayan Chakraborty, Antoine Dailly, FF, 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. [pdf | hal | arXiv (full version) | www]
[C31] FF, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and 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. [pdf | hal | www]
The full version is submitted to a journal.
[C30] FF, Clara Marcille, Zin Mar Myint, Sandeep RB, Sagnik Sen and S Taruni. Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity. Proceedings of the 10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2024), Lecture Notes in Computer Science 14508:29-43, 2024. [pdf | hal | www]
Two papers (paper 1 and paper 2) based on this paper are submitted to a journal.

2023

[J45] FF, Reza Naserasr and Rongxing Xu. Extended Double Covers and homomorphism bounds of signed graphs. The Electronic Journal of Combinatorics 30(3):P3.31, 2023. [pdf | arXiv | hal | www]
[J44] FF and Tuomo Lehtilä. Bounds and extremal graphs for total dominating identifying codes. The Electronic Journal of Combinatorics 30(3):P3.15, 2023. [pdf | arXiv | hal | www]
[J43] Subhadeep R. Dev, Sanjana Dey, FF, Ralf Klasing and Tuomo Lehtilä. The RED-BLUE SEPARATION problem on graphs. Theoretical Computer Science 970:114061, 2023. [pdf | arXiv | hal | www]
A preliminary conference version was presented at IWOCA 2022.
[J42] Sanjana Dey, FF, Subhas C. Nandy and Arunabha Sen. Complexity and approximation for discriminating and identifying code problems in geometric setups. Algorithmica 85(7):1850-1882, 2023. [pdf | arXiv | hal | www]
A preliminary conference version was presented at ISAAC 2020.

[C29] Dibyayan Chakraborty, FF and Anni Hakanen. Distance-based covering problems for graphs of given cyclomatic number. Proceedings of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023). Lecture Notes in Computer Science 14292:132-146, 2023. [pdf | hal | www]
The full version is submitted to a journal.
[C28] Antoine Dailly, FF and Anni Hakanen. Algorithms and hardness for Metric Dimension on digraphs. Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). Lecture Notes in Computer Science 14093:232-245, 2023. [pdf | hal | www]
The full version is submitted to a journal.
[C27] Dipayan Chakraborty, FF, and Tuomo Lehtilä. Identifying codes in bipartite graphs of given maximum degree. Proceedings of the 12th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023), Procedia Computer Science 223(2):157-165, 2023. [pdf | hal | www]
Two papers (paper 1 and paper 2) based on this paper are submitted to a journal.
[C26] Dibyayan Chakraborty, Jérémie Chalopin, FF and Yann Vaxès. Isometric path complexity of graphs. 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. [pdf | hal | www]
The full version is submitted to a journal.
[C25] Henning Fernau, FF, Kevin Mann, Utkarsh Padariya and Rajath Rao K.N.. Parameterizing path partitions. Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898:187-201, 2023. [pdf | hal | www]
The full version appeared in the journal Theoretical Computer Science.
[C24] Sandip Das, FF, Sk Samim Islam and Joydeep Mukherjee. Relation between broadcast domination and multipacking numbers on chordal graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:297-308, 2023. [pdf | hal | www]
The full version is submitted to a journal.
[C23] Dipayan Chakraborty, FF, Aline Parreau and Annegret K. Wagler. On three domination-based identification problems in block graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:271-283, 2023. [pdf | hal | www]
The full version appeared in the journal Fundamenta Informaticae in 2024.
[C22] FF, Krishna Narayanan and Lekshmi R S. Monitoring edge-geodetic sets in graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:245-256, 2023. [pdf | hal | www]
The full version is submitted to a journal.
[C21] Dipayan Chakraborty, FF, Soumen Nandi, Sagnik Sen and D K Supraja. New bounds and constructions for neighbor-locating colorings of graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:121-133, 2023. [pdf | hal | www]
The full version appeared in the journal Discrete Applied Mathematics in 2024.

2022

[J41] FF and Tuomo Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics 36(4):2619-2634, 2022. [pdf | hal | arXiv | www]
[J40] Laurent Beaudou, FF and Reza Naserasr. Smallest C2l+1-critical graphs of odd-girth 2k+1. Discrete Applied Mathematics 319:564-575, 2022. Special issue for CALDAM 2020. [pdf | hal | arXiv | www]
A preliminary conference version was presented at CALDAM 2020.
[J39] FF, Shih-Shun Kao, Ralf Klasing, Mirka Miller and Joe Ryan. Monitoring the edges of a graph using distances. Discrete Applied Mathematics 319:424-438, 2022. Special issue for CALDAM 2020. [pdf | hal | arXiv | www]
A preliminary conference version was presented at CALDAM 2020.
[J38] FF, Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron. Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity. Algorithmica 84(5):1183-1212, 2022. [pdf | hal | arXiv | www]
A preliminary conference version was presented at IPEC 2019.

[C20] Maël Dumas, FF, Anthony Perez and Ioan Todinca. On graphs coverable by k shortest paths. Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248,40:1-40:15, 2022. [pdf | hal | www]
The full version appeared in the journal SIAM Journal on Discrete Mathematics.
[C19] Dibyayan Chakraborty, Antoine Dailly, Sandip Das, FF, 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. [pdf | hal | www]
The full version is submitted to a journal.
[C18] Subhadeep R. Dev, Sanjana Dey, FF, Ralf Klasing and Tuomo Lehtilä. The RED-BLUE SEPARATION problem on graphs. Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), Lecture Notes in Computer Science 13270:285-298, 2022. [pdf | hal | www]
The full version appeared in the journal Theoretical Computer Science in 2023.

[P3] FF. Problems related to a conjecture on location-domination in twin-free graphs. Indian Journal of Discrete Mathematics 8(1):39-41, 2022. [pdf | hal | www]

2021

[J37] FF, Benjamin Gras, Anthony Perez and Florian Sikora. On the complexity of BROADCAST DOMINATION and MULTIPACKING in digraphs. Algorithmica 83(9):2651-2677, 2021. Special issue for selected papers of IWOCA 2020. [pdf | arXiv | hal | www]
A preliminary conference version was presented at IWOCA 2020.
[J36] FF, Narges Ghareghani, Aida Roshany-Tabrizi and Pouyeh Sharifani. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics 302:76-79, 2021. [pdf | hal | arXiv | www]
[J35] FF, Hervé Hocquard and Dimitri Lajou. Complexity and algorithms for injective edge-coloring in graphs. Information Processing Letters 170:106121, 2021. [pdf | hal | arXiv | www]
[J34] FF, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Éric Sopena and Petru Valicov. Exact square coloring of subcubic planar graphs. Discrete Applied Mathematics 293:74-89, 2021. [pdf | hal | arXiv | www]

[C17] FF, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr and Petru Valicov. Cliques in exact distance powers of graphs of given maximum degree. Proceedings of the 11th Latin and American Algorithms, Graphs and Optimisation Symposium (LAGOS 2021), Procedia Computer Science 195:427-436, 2021. [pdf | hal | www]

2020

[J33] François Dross, FF, Valia Mitsou, Pascal Ochem and Théo Pierron. Complexity of planar signed graph homomorphisms to cycles. Discrete Applied Mathematics 284:166-178, 2020. [pdf | hal | arXiv | www]
[J32] FF, Shahrzad Heydarshahi and Aline Parreau. Domination and location in twin-free digraphs. Discrete Applied Mathematics 284:42-52, 2020. [pdf | hal | arXiv | www]

[C16] Dibyayan Chakraborty, Sandip Das, FF, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,7:1-7:15, 2020. [pdf | arXiv (full version) | www]
A full version based on parts of this paper is submitted to a journal.
[C15] Sanjana Dey, FF, Subhas C. Nandy and Arunabha Sen. Discriminating codes in geometric setups. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,24:1-24:16, 2020. [pdf | www]
The full version appeared in the journal Algorithmica in 2023.
[C14] FF, Benjamin Gras, Anthony Perez and Florian Sikora. On the complexity of BROADCAST DOMINATION and MULTIPACKING in digraphs. Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), Lecture Notes in Computer Science 12126:264-276, 2020. [pdf | www]
The full version appeared in the journal Algorithmica in 2021.
[C13] Dibyayan Chakraborty, FF, Harmender Gahlawat, Subir Kumar Ghosh and Bodhayan Roy. Hardness and approximation for the geodetic set problem in some graph classes. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:102-115, 2020. [pdf | arXiv | www]
[C12] FF, Ralf Klasing, Mirka Miller and Joe Ryan. Monitoring the edges of a graph using distances. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:28-40, 2020. [pdf | hal | www]
The full version appeared in the journal Discrete Applied Mathematics in 2022.
[C11] Laurent Beaudou, FF and Reza Naserasr. Smallest C2l+1-critical graphs of odd-girth 2k+1. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Lecture Notes in Computer Science 12016:184-196, 2020. [pdf | www]
The full version appeared in the journal Discrete Applied Mathematics in 2022.

[P2] FF. Complexity of MULTIPACKING in graphs.
IWOCA Open Problem, 2020. [www]

2019

[J31] Antoine Dailly, FF and Adriana Hansberg. Strengthening the Murty-Simon conjecture on diameter 2 critical graphs. Discrete Mathematics 342(11):3142-3159, 2019. [pdf | hal | arXiv | www]
[J30] Laurent Beaudou, Richard C. Brewster and FF. Broadcast domination and multipacking: bounds and the integrality gap. The Australasian Journal of Combinatorics 74(1):86-97, 2019. [pdf | arXiv | hal | www]
[J29] Laurent Beaudou, FF and Reza Naserasr. Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colourings of 2k-regular K4-minor-free multigraphs. Discrete Applied Mathematics 261:40-51, 2019. Special issue for the 2016 GO X Meeting. [pdf | hal | arXiv | www]
[J28] Cristina Bazgan, FF and Florian Sikora. Parameterized and approximation complexity of PARTIAL VC DIMENSION. Theoretical Computer Science 766:1-15, 2019. [pdf | hal |arXiv | www]
A preliminary conference version was presented at COCOA 2016.

[C10] FF, Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron. Parameterized complexity of edge-coloured and signed graph homomorphism problems. Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Leibniz International Proceedings in Informatics 148,15:1-15:16, 2019. [pdf | www]
The full version appeared in the journal Algorithmica in 2022.
[C9] Laurent Beaudou, FF, Florent Madelaine, Lhouari Nourine and Gaétan Richard. Complexity of conjunctive regular path query homomorphisms. Proceedings of the 15th Conference on Computability in Europe (CIE 2019), Lecture Notes in Computer Science 11558:108-119, 2019. [pdf | hal | www]
The full version is submitted to a journal.

2018

[J27] Édouard Bonnet, FF, Eun Jung Kim and Florian Sikora. Complexity of Grundy coloring and its variants. Discrete Applied Mathematics 243:99-114, 2018. [pdf | hal | arXiv | www]
A preliminary conference version was presented at COCOON 2015.
[J26] Laurent Beaudou, Peter Dankelmann, FF, Michael A. Henning, Arnaud Mary and Aline Parreau. Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension. SIAM Journal on Discrete Mathematics 32(2):902-918, 2018. [hal | pdf | arXiv | www]

2017

[J25] FF and Ralf Klasing. Parameterized and approximation complexity of the detection pair problem in graphs. Journal of Graph Algorithms and Applications 21(6):1039-1056, 2017. [pdf | arXiv | www]
[J24] FF, Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis and Reza Naserasr. The complexity of tropical graph homomorphisms. Discrete Applied Mathematics 229:64-81, 2017. [pdf | hal (enhanced version) | arXiv (enhanced version) | www]
[J23] Laurent Beaudou, FF and Reza Naserasr. Homomorphism bounds and edge-colourings of K4-minor-free graphs. Journal of Combinatorial Theory, Series B 124:128-164, 2017. [pdf | arXiv | www]
[J22] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica 78(3):914-944, 2017. [pdf | arXiv | www]
A preliminary conference version was presented at WG 2015.
[J21] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science 668:43-58, 2017. [pdf | arXiv | www]
[J20] Olivier Baudon, Julien Bensmail, FF and Monika Pilśniak. Structural properties of recursively partitionable graphs with connectivity 2. Discussiones Mathematicae Graph Theory 37(1):89-115, 2017. [pdf | hal | www]
[J19] FF, Guillem Perarnau and Oriol Serra. Random subgraphs make identification affordable. Journal of Combinatorics 8(1):57-77, 2017. [pdf | arXiv | www]
A preliminary conference version was presented at EUROCOMB 2013.
[J18] Richard C. Brewster, FF, Pavol Hell and Reza Naserasr. The complexity of signed and edge-coloured graph homomorphisms. Discrete Mathematics 340(2):223-235, 2017. [pdf | arXiv | www]
[J17] FF and Michael A. Henning. Location-domination in line graphs. Discrete Mathematics 340(1):3140-3153, 2017. [pdf | arXiv | www]

2016

[J16] FF and Michael A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics 23(3):P3.9, 2016. [pdf | arXiv | www]
[J15] FF and Michael A. Henning. Location-domination and matching in cubic graphs. Discrete Mathematics 339(4):1221-1231, 2016. [pdf | arXiv | www]
[J14] FF, Michael A. Henning, Christian Löwenstein and Thomas Sasse. Locating-dominating sets in twin-free graphs. Discrete Applied Mathematics 200:52-58, 2016. [pdf | arXiv | www]

[C8] Cristina Bazgan, FF and Florian Sikora. On the approximability of PARTIAL VC DIMENSION. Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Lecture Notes in Computer Science 10043:92-106, 2016. [pdf | www]
The full version appeared in the journal Theoretical Computer Science in 2019.

2015

[J13] Camino Balbuena, FF and Adriana Hansberg. Locating-dominating sets and identifying codes in graphs of girth at least 5. The Electronic Journal of Combinatorics 22(2):P2.15, 2015. [pdf | arXiv | www]
[J12] FF. Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. Journal of Discrete Algorithms 31:48-68, 2015. Special issue for selected papers of IWOCA 2013. [pdf | hal | www]
A preliminary conference version was presented at IWOCA 2013.
[J11] FF, Michael Krivelevich and Guillem Perarnau. Large subgraphs without short cycles. SIAM Journal on Discrete Mathematics 29(1):65-78, 2015. [pdf | arXiv | www]

[C7] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov. Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Lecture Notes in Computer Science 9224:456-471, 2016. [pdf | hal | www]
The full version appeared in the journal Algorithmica in 2017.
[C6] Édouard Bonnet, FF, Eun Jung Kim and Florian Sikora. Complexity of Grundy coloring and its variants. Proceedings of the 21st International Conference on Computing and Combinatorics (COCOON 2015), Lecture Notes in Computer Science 9198:109-120, 2015. [pdf | www]
The full version appeared in the journal Discrete Applied Mathematics in 2018.

[U2] FF, Reza Naserasr, Aline Parreau and Petru Valicov. On powers of interval graphs and their orders. Unpublished manuscript, 2015. [arXiv]

2014

[J10] FF, Ralf Klasing and Peter J. Slater. Centroidal bases in graphs. Networks 64(2):96-108, 2014. [pdf | arXiv | www]
[J9] FF, Tero Laihonen and Aline Parreau. An improved lower bound for (1,<=2)-identifying codes in the king grid. Advances in Mathematics of Communications 8(1):35-52, 2014. [pdf | hal | arXiv | www]
[J8] Olivier Baudon, FF, Jakub Przybyło and Mariusz Woźniak. On the structure of arbitrarily partitionable graphs with given connectivity. Discrete Applied Mathematics 162:381-385, 2014. [pdf | hal | www]

[C5] FF and Reza Naserasr. The complexity of signed graph homomorphisms and signed constraint satisfaction. Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014), Lecture Notes in Computer Science 8392:526-537, 2014. [pdf | www]

2013

[J7] FF and Matjaž Kovše. Identifying path covers in graphs. Journal of Discrete Algorithms 23:21-34, 2013. Special issue for selected papers of IWOCA 2012. [pdf | hal | www]
A preliminary conference version was presented at IWOCA 2012.
[J6] FF, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov. Identifying codes in line graphs. Journal of Graph Theory 73(4):425-448, 2013. [pdf | hal | arXiv | www]
A preliminary conference version was presented at EUROCOMB 2011.
[J5] FF, Reza Naserasr and Aline Parreau. Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets. Graphs and Combinatorics 29(3):463-473, 2013. [pdf | hal | arXiv | www]

[C4] FF, Guillem Perarnau and Oriol Serra. Random subgraphs make identification affordable. Proceedings of the 7th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2013), CRM Series 16:415-420, 2013. [pdf | www]
The full version appeared in the journal Journal of Combinatorics in 2017.
[C3] FF. The complexity of the identifying code problem in restricted graph classes. Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), Lecture Notes in Computer Science 8288:150-163, 2013. [pdf | www]
The full version appeared in the journal Journal of Discrete Algorithms in 2015.

2012

[J4] FF, Ralf Klasing, Adrian Kosowski and André Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics 160(10-11):1532-1546, 2012. [pdf | hal | arXiv | www]
[J3] FF, Iiro Honkala, Tero Laihonen, Aline Parreau and Guillem Perarnau. Locally identifying colourings for graphs with given maximum degree. Discrete Mathematics 312(10):1832-1837, 2012. [pdf | hal | arXiv | www]
[J2] FF and Guillem Perarnau. Bounds on identifying codes in terms of degree parameters. The Electronic Journal of Combinatorics 19:P32, 2012. [pdf | hal | arXiv | www]

[C2] FF and Matjaž Kovše. On graph identification problems and the special case of identifying vertices using paths. Proceedings of the 23rd International Workshop on Combinatorial Algorithms (IWOCA 2012), Lecture Notes in Computer Science 7643:32-45, 2012. [pdf | www]
The full version appeared in the journal Journal of Discrete Algorithms in 2013.

[P1] FF. The complexity of covering a ladder using cycles.
IWOCA Open Problem, 2012. [www]

2011

[J1] FF, Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau and Petru Valicov. Extremal graphs for the identifying code problem. European Journal of Combinatorics 32(4):628-638, 2011. [pdf | hal | arXiv | www]

[C1] FF, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov. Edge identifying codes. Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2011), Electronic Notes in Discrete Mathematics 38:343-348, 2011. [pdf | www]
The full version appeared in the journal Journal of Graph Theory in 2013.

[U1] FF, Aline Parreau and Petru Valicov. Locally identifying colouring planar graphs of small maximum degree and girth 5 with four colours is NP-hard. Unpublished manuscript, 2011. [pdf]

Theses

FF. Combinatorial and algorithmic aspects of identifying codes in graphs. PhD Thesis, defended on December 10th, 2012 at Université Bordeaux 1. Under the supervision of Ralf Klasing and André Raspaud. In English. [Manuscript (Clickable colour PDF) | Manuscript (Printable Black&White PDF) | Slides of the defense (PDF)]
FF. Identifying codes in special graph classes. Master's thesis, Université Bordeaux 1, June 2009. Under the supervision of Ralf Klasing and André Raspaud. In English, with French introduction. [Manuscript (PDF)]

Other material

FF. Report on the Extended Stay Support Scheme for STACS 2024 (March 12-14, 2024) in Clermont-Ferrand, France. [pdf]
FF, Leszek A. Gąsieniec, Ralf Klasing, Tomasz Radzik and William F. Smyth. IWOCA 2020 in Bordeaux (Oops! On-line!). [pdf]
Bulletin of the EATCS 132:73-76, 2020. [www]
IFIP News, September 2020, pp. 9-10. [pdf]
IFORS News, September 2020, pp. 24-25. [pdf]

Navigate up: Research papers - Theses - Other material

FlorentFoucaud

Wandering researcher and teacher