Skip to Main content
Number of documents

60

CV Florent Foucaud


Journal articles37 documents

  • Florent Foucaud, Shih-Shun Kao, Ralf Klasing, Mirka Miller, Joe Ryan. Monitoring the edges of a graph using distances. Discrete Applied Mathematics, Elsevier, 2022, Combined Special Issue: 1) Algorithms and Discrete Applied Mathematics (CALDAM 2019); Guest edited by Swami Sarvottamananda and Sudebkumar Prasant Pal 2) Algorithms and Discrete Applied Mathematics (CALDAM 2020); Guest edited by Manoj Changat and Sandip Das, 319, pp.425-438. ⟨hal-03043870v2⟩
  • Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron. Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity. Algorithmica, Springer Verlag, 2022, 84 (5), pp.1183-1212. ⟨10.1007/s00453-021-00918-4⟩. ⟨hal-03658581⟩
  • Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, et al.. Exact square coloring of subcubic planar graphs. Discrete Applied Mathematics, Elsevier, 2021, 293, pp.74-89. ⟨10.1016/j.dam.2021.01.007⟩. ⟨hal-02925881v3⟩
  • Florent Foucaud, Narges Ghareghani, Aida Roshany-Tabrizi, Pouyeh Sharifani. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics, Elsevier, 2021, 302, pp.76-79. ⟨10.1016/j.dam.2021.06.006⟩. ⟨hal-03540625⟩
  • Laurent Beaudou, Florent Foucaud, Reza Naserasr. Smallest $C_{2l+1}$-critical graphs of odd-girth $2k+1$. Discrete Applied Mathematics, Elsevier, 2021, 319, pp.564 - 575. ⟨10.1016/j.dam.2021.08.040⟩. ⟨hal-03784719⟩
  • Florent Foucaud, Hervé Hocquard, Dimitri Lajou. Complexity and algorithms for injective edge-coloring in graphs. Information Processing Letters, Elsevier, 2021, 170, pp.106121. ⟨10.1016/j.ipl.2021.106121⟩. ⟨hal-03201544⟩
  • Florent Foucaud, Shahrzad Heydarshahi, Aline Parreau. Domination and location in twin-free digraphs. Discrete Applied Mathematics, Elsevier, 2020, 284, pp.42-52. ⟨10.1016/j.dam.2020.03.025⟩. ⟨hal-03041356⟩
  • François Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem, Théo Pierron. Complexity of planar signed graph homomorphisms to cycles. Discrete Applied Mathematics, Elsevier, 2020, 284, pp.166-178. ⟨10.1016/j.dam.2020.03.029⟩. ⟨hal-02990576⟩
  • Laurent Beaudou, Florent Foucaud, Reza Naserasr. Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colorings of 2k-regular K4-minor-free multigraphs. Discrete Applied Mathematics, Elsevier, 2019, 261, pp.40-51. ⟨10.1016/j.dam.2018.09.004⟩. ⟨hal-01915269⟩
  • Antoine Dailly, Florent Foucaud, Adriana Hansberg. Strengthening the Murty-Simon conjecture on diameter 2 critical graphs. Discrete Mathematics, Elsevier, 2019, 342 (11), pp.3142-3159. ⟨10.1016/j.disc.2019.06.023⟩. ⟨hal-01959683⟩
  • Laurent Beaudou, Richard C. Brewster, Florent Foucaud. Broadcast domination and multipacking: bounds and the integrality gap. The Australasian Journal of Combinatorics, Combinatorial Mathematics Society of Australasia (Inc.), 2019, 74 (1), pp.86-97. ⟨hal-03041313⟩
  • Laurent Beaudou, Peter Dankelmann, Florent Foucaud, Michael Antony Henning, Arnaud Mary, et al.. 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, Society for Industrial and Applied Mathematics, 2018, 32 (2), pp.902 - 918. ⟨10.1137/16M1097833⟩. ⟨hal-01848648⟩
  • Edouard Bonnet, Foucaud Florent, Eunjung Kim, Florian Sikora. Complexity of Grundy coloring and its variants. Discrete Applied Mathematics, Elsevier, 2018. ⟨hal-01991659⟩
  • Florent Foucaud, Guillem Perarnau, Oriol Serra. Random subgraphs make identification affordable. Journal of Combinatorics, International Press, 2017, 8 (1), pp.57-77. ⟨10.4310/JOC.2017.v8.n1.a3⟩. ⟨hal-03041297⟩
  • Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, Springer Verlag, 2017, 78 (3), pp.914-944. ⟨10.1007/s00453-016-0184-1⟩. ⟨hal-01198784⟩
  • Florent Foucaud, Michael Henning. Location-domination in line graphs. Discrete Mathematics, Elsevier, 2017, 340 (1), pp.3140-3153. ⟨10.1016/j.disc.2016.05.020⟩. ⟨hal-03041286⟩
  • Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilsniak. Structural properties of recursively partitionable graphs with connectivity 2. Discussiones Mathematicae Graph Theory, University of Zielona Góra, 2017, 37, pp.89-115. ⟨10.7151/dmgt.1925⟩. ⟨hal-00672505v4⟩
  • Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, Elsevier, 2017, 668, pp.43-58. ⟨10.1016/j.tcs.2017.01.006⟩. ⟨hal-01198783⟩
  • Laurent Beaudou, Florent Foucaud, Reza Naserasr. Homomorphism bounds and edge-colourings of K4-minor-free graphs. Journal of Combinatorial Theory, Series B, Elsevier, 2017, 124, pp.128-164. ⟨10.1016/j.jctb.2017.01.001⟩. ⟨hal-01520741⟩
  • Florent Foucaud, Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis, et al.. The complexity of tropical graph homomorphisms.. Discrete Applied Mathematics, Elsevier, 2017, 229, pp.64-81. ⟨10.1016/j.dam.2017.04.027⟩. ⟨hal-01520739⟩
  • Florent Foucaud, Ralf Klasing. Parameterized and approximation complexity of the detection pair problem in graphs. Journal of Graph Algorithms and Applications, Brown University, 2017, 21 (6), pp.1039 - 1056. ⟨10.7155/jgaa.00449⟩. ⟨hal-01871140⟩
  • Florent Foucaud, Michael Henning, Christian Löwenstein, Thomas Sasse. Locating–dominating sets in twin-free graphs. Discrete Applied Mathematics, Elsevier, 2016, 200, pp.52-58. ⟨10.1016/j.dam.2015.06.038⟩. ⟨hal-03041273⟩
  • Florent Foucaud, Michael A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics, Open Journal Systems, 2016, 23 (3), pp.P3.9. ⟨hal-03041282⟩
  • Florent Foucaud, Michael Henning. Location-domination and matching in cubic graphs. Discrete Mathematics, Elsevier, 2016, 339 (4), pp.1221-1231. ⟨10.1016/j.disc.2015.11.016⟩. ⟨hal-03041274⟩
  • Camino Balbuena, Florent Foucaud, Adriana Hansberg. Locating-dominating sets and identifying codes in graphs of girth at least 5. The Electronic Journal of Combinatorics, Open Journal Systems, 2015, 22 (2), pp.P2.15. ⟨hal-03041268⟩
  • Florent Foucaud, M. Krivelevich, G. Perarnau. Large Subgraphs without Short Cycles. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2015, 29 (1), pp.65-78. ⟨10.1137/140954416⟩. ⟨hal-03041235⟩
  • Florent Foucaud. Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. Journal of Discrete Algorithms, Elsevier, 2015, 31, pp.48-68. ⟨hal-00923356⟩
  • Olivier Baudon, Florent Foucaud, Jakub Przybylo, Mariusz Woźniak. On the structure of arbitrarily partitionable graphs with given connectivity. Discrete Applied Mathematics, Elsevier, 2014, 162, pp.381-385. ⟨10.1016/j.dam.2013.09.007⟩. ⟨hal-00918947⟩
  • Florent Foucaud, Ralf Klasing, Peter J. Slater. Centroidal bases in graphs. Networks, Wiley, 2014, 64 (2), pp.96-108. ⟨10.1002/net.21560⟩. ⟨hal-01428804⟩
  • Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for (1,<=2)-identifying codes in the king grid. Advances in Mathematics of Communications, AIMS, 2014, 8 (1), pp.35-52. ⟨10.3934/amc.2014.8.35⟩. ⟨hal-00639998⟩
  • Florent Foucaud, Reza Naserasr, Aline Parreau. Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets. Graphs and Combinatorics, Springer Verlag, 2013, 29 (3), pp.463-473. ⟨10.1007/s00373-012-1136-4⟩. ⟨hal-00526446v3⟩
  • Florent Foucaud, Matjaz Kovse. Identifying path covers in graphs. Journal of Discrete Algorithms, Elsevier, 2013, 23, pp.21-34. ⟨10.1016/j.jda.2013.07.006⟩. ⟨hal-00957969⟩
  • Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov. Identifying codes in line graphs. Journal of Graph Theory, Wiley, 2013, 73 (4), pp.425-448. ⟨10.1002/jgt.21686⟩. ⟨hal-00605406v2⟩
  • Florent Foucaud, Iiro Honkala, Tero Laihonen, Aline Parreau, Guillem Perarnau. Locally identifying colourings for graphs with given maximum degree. Discrete Mathematics, Elsevier, 2012, 312 (10), pp.1832--1837. ⟨10.1016/j.disc.2012.01.034⟩. ⟨hal-00614513v2⟩
  • Florent Foucaud, Guillem Perarnau. Bounds for identifying codes in terms of degree parameters. The Electronic Journal of Combinatorics, Open Journal Systems, 2012, 19, pp.P32. ⟨hal-00578230v5⟩
  • Florent Foucaud, Ralf Klasing, Adrian Kosowski, André Raspaud. On the size of identifying codes in triangle-free graphs. Discrete Applied Mathematics, Elsevier, 2012, 160 (10-11), pp.1532-1546. ⟨10.1016/j.dam.2012.02.009⟩. ⟨hal-00530172v3⟩
  • Florent Foucaud, Eleonora Guerrini, Matjaz Kovse, Reza Naserasr, Aline Parreau, et al.. Extremal graphs for the identifying code problem. European Journal of Combinatorics, Elsevier, 2011, 32 (4), pp.628-638. ⟨10.1016/j.ejc.2011.01.002⟩. ⟨hal-00477467v4⟩

Conference papers16 documents

  • Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing, Tuomo Lehtilä. The Red-Blue Separation Problem on Graphs. IWOCA 2022, Jun 2022, Trier, Germany. pp.285-298, ⟨10.1007/978-3-031-06678-8_21⟩. ⟨hal-03711361⟩
  • Florent Foucaud, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Petru Valicov. Cliques in exact distance powers of graphs of given maximum degree. LAGOS 2021 - 11th Latin and American Algorithms, Graphs and Optimisation Symposium, May 2021, Sao Paulo, Brazil. pp.427-436, ⟨10.1016/j.procs.2021.11.052⟩. ⟨hal-03540673⟩
  • Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh, Bodhayan Roy. Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes. 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Feb 2020, Hyderabad, India. pp.102-115, ⟨10.1007/978-3-030-39219-2_9⟩. ⟨hal-03041353⟩
  • Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora. On the Complexity of Broadcast Domination and Multipacking in Digraphs. Combinatorial Algorithms - 31st International Workshop, Jun 2020, Bordeaux, France. pp.264-276, ⟨10.1007/978-3-030-48966-3_20⟩. ⟨hal-02793880⟩
  • Laurent Beaudou, Florent Foucaud, Reza Naserasr. Smallest $C_{2l+1}$-Critical Graphs of Odd-Girth $2k+1$. 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Feb 2020, Hyderabad, India. pp.184-196, ⟨10.1007/978-3-030-39219-2_16⟩. ⟨hal-03041342⟩
  • Florent Foucaud, Ralf Klasing, Mirka Miller, Joe Ryan. Monitoring the edges of a graph using distances. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020), Feb 2020, Hyderabad, India. pp.28-40, ⟨10.1007/978-3-030-39219-2_3⟩. ⟨hal-02500423⟩
  • Sanjana Dey, Florent Foucaud, Subhas C Nandy, Arunabha Sen. Discriminating Codes in Geometric Setups. 31st International Symposium on Algorithms and Computation (ISAAC 2020), Dec 2020, Hong-Kong, Hong Kong SAR China. pp.24:1-16, ⟨10.4230/LIPIcs.ISAAC.2020.24⟩. ⟨hal-03041359⟩
  • Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, et al.. Algorithms and complexity for geodetic sets on planar and chordal graphs. 31st International Symposium on Algorithms and Computation (ISAAC 2020), Dec 2020, Hong-Kong, Hong Kong SAR China. pp.7:1-15, ⟨10.4230/LIPIcs.ISAAC.2020.7⟩. ⟨hal-03041361⟩
  • Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Theo Pierron. Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems. IPEC 2019, Sep 2019, Munich, Germany. pp.15:1-16, ⟨10.4230/LIPIcs.IPEC.2019.15⟩. ⟨hal-02491871⟩
  • Cristina Bazgan, Florent Foucaud, Florian Sikora. On the Approximability of Partial VC Dimension. 10th International Conference, COCOA 2016, Dec 2016, Hong Kong, China. pp.92-106, ⟨10.1007/978-3-319-48749-6_7⟩. ⟨hal-01431728⟩
  • Edouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora. Complexity of Grundy Coloring and Its Variants. 21st International Conference on Computing and Combinatorics, COCOON 2015, Aug 2015, Beijing, China. pp.109-120, ⟨10.1007/978-3-319-21398-9_9⟩. ⟨hal-01370531⟩
  • Florent Foucaud, George Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov. Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs. International Workshop on Graph-Theoretic Concepts in Computer Science WG 2015, Jun 2015, Munich, Germany. pp.175 - 471, ⟨10.1007/978-3-662-53174-7_32⟩. ⟨hal-01518713⟩
  • Florent Foucaud, Guillem Perarnau, Oriol Serra. Random subgraphs make identification affordable. 7th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2013), Sep 2013, Pisa, Italy. pp.415-420, ⟨10.1007/978-88-7642-475-5_66⟩. ⟨hal-03041296⟩
  • Florent Foucaud. The complexity of the identifying code problem in restricted graph classes. International Workshop on Combinatorial Algorithms (IWOCA), Jul 2013, Rouen, France. pp.150-163, ⟨10.1007/978-3-642-45278-9_14⟩. ⟨hal-00960564⟩
  • Florent Foucaud, Matjaž Kovše. On graph identification problems and the special case of identifying vertices using paths. International Workshop on Combinatorial Algorithms (IWOCA), Jul 2012, Krishnankoil, India. pp.32-45, ⟨10.1007/978-3-642-35926-2_4⟩. ⟨hal-00960561⟩
  • Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov. Edge identifying codes. European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), Aug 2011, Budapest, Hungary. pp.343-348, ⟨10.1016/j.endm.2011.09.056⟩. ⟨hal-00960555⟩

Preprints, Working Papers, ...5 documents

  • Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, et al.. Complexity and algorithms for Isometric Path Cover on chordal graphs and beyond. 2022. ⟨hal-03710812⟩
  • Florent Foucaud, Reza Naserasr, Rongxing Xu. Extended Double Covers and Homomorphism Bounds of Signed Graphs *. 2021. ⟨hal-03356591⟩
  • Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, et al.. Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. 2021. ⟨hal-03406709⟩
  • Florent Foucaud, Reza Naserasr, Aline Parreau, Petru Valicov. On powers of interval graphs and their orders. 2015. ⟨hal-01198830⟩
  • Olivier Baudon, Florent Foucaud, Jakub Przybylo, Mariusz Woźniak. On the structure of arbitrarily partitionable graphs with given connectivity. 2012. ⟨hal-00690253v9⟩

Reports1 document

  • Olivier Baudon, Florent Foucaud, Monika Pilsniak. A note on online and recursively arbitrarily vertex-partitionable balloons. 2012. ⟨hal-00656232⟩

Theses1 document

  • Florent Foucaud. Combinatorial and algorithmic aspects of identifying codes in graphs. Data Structures and Algorithms [cs.DS]. Université Sciences et Technologies - Bordeaux I, 2012. English. ⟨tel-00766138⟩