Florent Foucaud

According to our database, Florent Foucaud authored at least 93 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Neighbourhood complexity of graphs of bounded twin-width.

Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau

Eur. J. Comb., January, 2024

On Graphs Coverable by <i>k</i> Shortest Paths.

Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca

SIAM J. Discret. Math., 2024

On Three Domination-based Identification Problems in Block Graphs.

Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret Wagler

Fundam. Informaticae, 2024

Progress towards the two-thirds conjecture on locating-total dominating sets.

Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael A. Henning, Annegret Katrin Wagler

Discret. Math., 2024

Extremal digraphs for open neighbourhood location-domination and identifying codes.

Florent Foucaud, Narges Ghareghani, Pouyeh Sharifani

Discret. Appl. Math., 2024

On locating and neighbor-locating colorings of sparse graphs.

Dipayan Chakraborty, Florent Foucaud, Soumen Nandi, Sagnik Sen, D. K. Supraja

Discret. Appl. Math., 2024

Algorithms and complexity for monitoring edge-geodetic sets in graphs.

Florent Foucaud, Clara Marcille, R. B. Sandeep, Sagnik Sen, S. Taruni

CoRR, 2024

Monitoring arc-geodetic sets of oriented graphs.

Tapas Das, Florent Foucaud, Clara Marcille, Pavan P. D, Sagnik Sen

CoRR, 2024

Metric Dimension and Geodetic Set Parameterized by Vertex Cover.

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

CoRR, 2024

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs.

Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R. B. Sandeep, Sagnik Sen, S. Taruni

CoRR, 2024

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?

Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing

CoRR, 2024

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover.

Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, Prafullkumar Tale

CoRR, 2024

Algorithms and Complexity for Path Covers of Temporal DAGs.

Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover.

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Monitoring Edge-Geodetic Sets in Graphs: Extremal Graphs, Bounds, Complexity.

Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R. B. Sandeep, Sagnik Sen, S. Taruni

Proceedings of the Algorithms and Discrete Applied Mathematics, 2024

2023

The RED-BLUE SEPARATION problem on graphs.

Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing, Tuomo Lehtilä

Theor. Comput. Sci., August, 2023

Complexity and Approximation for Discriminating and Identifying Code Problems in Geometric Setups.

Sanjana Dey, Florent Foucaud, Subhas C. Nandy, Arunabha Sen

Algorithmica, July, 2023

Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs.

Sandip Das, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee

CoRR, 2023

Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations.

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

CoRR, 2023

Isometric path antichain covers: beyond hyperbolic graphs.

Dibyayan Chakraborty, Florent Foucaud

CoRR, 2023

Extended Double Covers and Homomorphism Bounds of Signed Graphs.

Florent Foucaud, Reza Naserasr, Rongxing Xu

Electron. J. Comb., 2023

Bounds and Extremal Graphs for Total Dominating Identifying Codes.

Florent Foucaud, Tuomo Lehtilä

Electron. J. Comb., 2023

Algorithms and Hardness for Metric Dimension on Digraphs.

Antoine Dailly, Florent Foucaud, Anni Hakanen

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

Isometric Path Complexity of Graphs.

Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, Yann Vaxès

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Identifying codes in bipartite graphs of given maximum degree.

Dipayan Chakraborty, Florent Foucaud, Tuomo Lehtilä

Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023

Distance-Based Covering Problems for Graphs of Given Cyclomatic Number.

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen

Proceedings of the Fundamentals of Computation Theory - 24th International Symposium, 2023

Parameterizing Path Partitions.

Henning Fernau, Florent Foucaud, Kevin Mann, Utkarsh Padariya, Rajath Rao K. N

Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

Monitoring Edge-Geodetic Sets in Graphs.

Florent Foucaud, Krishna Narayanan, Lekshmi Ramasubramony Sulochana

Proceedings of the Algorithms and Discrete Applied Mathematics, 2023

Relation Between Broadcast Domination and Multipacking Numbers on Chordal Graphs.

Sandip Das, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee

Proceedings of the Algorithms and Discrete Applied Mathematics, 2023

New Bounds and Constructions for Neighbor-Locating Colorings of Graphs.

Dipayan Chakraborty, Florent Foucaud, Soumen Nandi, Sagnik Sen, D. K. Supraja

Proceedings of the Algorithms and Discrete Applied Mathematics, 2023

2022

Revisiting and Improving Upper Bounds for Identifying Codes.

Florent Foucaud, Tuomo Lehtilä

SIAM J. Discret. Math., December, 2022

Monitoring the edges of a graph using distances.

Florent Foucaud, Shih-Shun Kao, Ralf Klasing, Mirka Miller, Joe Ryan

Discret. Appl. Math., 2022

Smallest C2ℓ+1-critical graphs of odd-girth 2k+1.

Laurent Beaudou, Florent Foucaud, Reza Naserasr

Discret. Appl. Math., 2022

Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity.

Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron

Algorithmica, 2022

On Graphs Coverable by k Shortest Paths.

Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond.

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

Complexity and algorithms for injective edge-coloring in graphs.

Florent Foucaud, Hervé Hocquard, Dimitri Lajou

Inf. Process. Lett., 2021

Exact square coloring of subcubic planar graphs.

Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Éric Sopena, Petru Valicov

Discret. Appl. Math., 2021

Characterizing extremal graphs for open neighbourhood location-domination.

Florent Foucaud, Narges Ghareghani, Aida Roshany-Tabrizi, Pouyeh Sharifani

Discret. Appl. Math., 2021

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly.

Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor

CoRR, 2021

On the Complexity of Broadcast Domination and Multipacking in Digraphs.

Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora

Algorithmica, 2021

Cliques in exact distance powers of graphs of given maximum degree.

Florent Foucaud, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Petru Valicov

Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

2020

IWOCA 2020 in Bordeaux (Oops! On-Line!).

Florent Foucaud, Leszek Gasieniec, Ralf Klasing, Tomasz Radzik, Bill Smyth

Bull. EATCS, 2020

Domination and location in twin-free digraphs.

Florent Foucaud, Shahrzad Heydarshahi, Aline Parreau

Discret. Appl. Math., 2020

Complexity of planar signed graph homomorphisms to cycles.

François Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem, Théo Pierron

Discret. Appl. Math., 2020

Discriminating Codes in Geometric Setups.

Sanjana Dey, Florent Foucaud, Subhas C. Nandy, Arunabha Sen

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs.

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, Bodhayan Roy

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Monitoring the Edges of a Graph Using Distances.

Florent Foucaud, Ralf Klasing, Mirka Miller, Joe Ryan

Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes.

Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir Kumar Ghosh, Bodhayan Roy

Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

Smallest C_2l+1-Critical Graphs of Odd-Girth 2k+1.

Laurent Beaudou, Florent Foucaud, Reza Naserasr

Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

2019

Parameterized and approximation complexity of Partial VC Dimension.

Cristina Bazgan, Florent Foucaud, Florian Sikora

Theor. Comput. Sci., 2019

Strengthening the Murty-Simon conjecture on diameter 2 critical graphs.

Antoine Dailly, Florent Foucaud, Adriana Hansberg

Discret. Math., 2019

Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colorings of 2k-regular K4-minor-free multigraphs.

Laurent Beaudou, Florent Foucaud, Reza Naserasr

Discret. Appl. Math., 2019

Broadcast domination and multipacking: bounds and the integrality gap.

Laurent Beaudou, Richard C. Brewster, Florent Foucaud

Australas. J Comb., 2019

Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems.

Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Complexity of Conjunctive Regular Path Query Homomorphisms.

Laurent Beaudou, Florent Foucaud, Florent R. Madelaine, Lhouari Nourine, Gaétan Richard

Proceedings of the Computing with Foresight and Industry, 2019

2018

Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension.

Laurent Beaudou, Peter Dankelmann, Florent Foucaud, Michael A. Henning, Arnaud Mary, Aline Parreau

SIAM J. Discret. Math., 2018

Complexity of Grundy coloring and its variants.

Édouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora

Discret. Appl. Math., 2018

2017

Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds.

Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov

Theor. Comput. Sci., 2017

Parameterized and approximation complexity of the detection pair problem in graphs.

Florent Foucaud, Ralf Klasing

J. Graph Algorithms Appl., 2017

Homomorphism bounds and edge-colourings of K₄-minor-free graphs.

Laurent Beaudou, Florent Foucaud, Reza Naserasr

J. Comb. Theory B, 2017

Structural properties of recursively partitionable graphs with connectivity 2.

Olivier Baudon, Julien Bensmail, Florent Foucaud, Monika Pilsniak

Discuss. Math. Graph Theory, 2017

Location-domination in line graphs.

Florent Foucaud, Michael A. Henning

Discret. Math., 2017

The complexity of signed graph and edge-coloured graph homomorphisms.

Richard C. Brewster, Florent Foucaud, Pavol Hell, Reza Naserasr

Discret. Math., 2017

The complexity of tropical graph homomorphisms.

Florent Foucaud, Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis, Reza Naserasr

Discret. Appl. Math., 2017

Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity.

Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov

Algorithmica, 2017

2016

Location-domination and matching in cubic graphs.

Florent Foucaud, Michael A. Henning

Discret. Math., 2016

Locating-dominating sets in twin-free graphs.

Florent Foucaud, Michael A. Henning, Christian Löwenstein, Thomas Sasse

Discret. Appl. Math., 2016

Locating-Total Dominating Sets in Twin-Free Graphs: a Conjecture.

Florent Foucaud, Michael A. Henning

Electron. J. Comb., 2016

On the Approximability of Partial VC Dimension.

Cristina Bazgan, Florent Foucaud, Florian Sikora

Proceedings of the Combinatorial Optimization and Applications, 2016

2015

Large Subgraphs without Short Cycles.

Florent Foucaud, Michael Krivelevich, Guillem Perarnau

SIAM J. Discret. Math., 2015

Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes.

Florent Foucaud

J. Discrete Algorithms, 2015

The complexity of signed graph and 2-edge-coloured graph homomorphisms.

Richard C. Brewster, Florent Foucaud, Pavol Hell, Reza Naserasr

CoRR, 2015

Locating-Dominating Sets and Identifying Codes in Graphs of Girth at least 5.

Camino Balbuena, Florent Foucaud, Adriana Hansberg

Electron. J. Comb., 2015

Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs.

Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

2014

Centroidal bases in graphs.

Florent Foucaud, Ralf Klasing, Peter J. Slater

Networks, 2014

On the structure of arbitrarily partitionable graphs with given connectivity.

Olivier Baudon, Florent Foucaud, Jakub Przybylo, Mariusz Wozniak

Discret. Appl. Math., 2014

Identification, location-domination and metric dimension on interval and permutation graphs.

Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov

CoRR, 2014

An improved lower bound for (1, ≤ 2)-identifying codes in the king grid.

Florent Foucaud, Tero Laihonen, Aline Parreau

Adv. Math. Commun., 2014

The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction.

Florent Foucaud, Reza Naserasr

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013

Identifying Codes in Line Graphs.

Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov

J. Graph Theory, 2013

Identifying path covers in graphs.

Florent Foucaud, Matjaz Kovse

J. Discrete Algorithms, 2013

Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy's Theorem on Induced Subsets.

Florent Foucaud, Reza Naserasr, Aline Parreau

Graphs Comb., 2013

Random subgraphs make identification affordable.

Florent Foucaud, Guillem Perarnau, Oriol Serra

CoRR, 2013

The Complexity of the Identifying Code Problem in Restricted Graph Classes.

Florent Foucaud

Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

2012

Combinatorial and algorithmic aspects of identifying codes in graphs. (Aspects combinatoires et algorithmiques des codes identifiants dans les graphes).

Florent Foucaud

PhD thesis, 2012

Locally identifying colourings for graphs with given maximum degree.

Florent Foucaud, Iiro S. Honkala, Tero Laihonen, Aline Parreau, Guillem Perarnau

Discret. Math., 2012

On the size of identifying codes in triangle-free graphs.

Florent Foucaud, Ralf Klasing, Adrian Kosowski, André Raspaud

Discret. Appl. Math., 2012

Bounds for Identifying Codes in Terms of Degree Parameters.

Florent Foucaud, Guillem Perarnau

Electron. J. Comb., 2012

On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths.

Florent Foucaud, Matjaz Kovse

Proceedings of the Combinatorial Algorithms, 23rd International Workshop, 2012

2011

Edge identifying codes.

Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau, Petru Valicov

Electron. Notes Discret. Math., 2011

Extremal graphs for the identifying code problem.

Florent Foucaud, Eleonora Guerrini, Matjaz Kovse, Reza Naserasr, Aline Parreau, Petru Valicov

Eur. J. Comb., 2011

2010

Extremal problems on identifying codes in digraphs and Bondy's theorem on induced subsets

Florent Foucaud, Reza Naserasr, Aline Parreau

CoRR, 2010